CS 210: Data Structures and Algorithms Lecture Notes

Introduction

• Instructor: Dr. Daniel Page (call him Daniel or Dan)
• Email: [email protected]
• Office Hours: Scheduled during the week, accessible via Zoom link on the course website.

Course Overview

• Course Name: Data Structures and Algorithms (CS 210)
• Compressed Course: More frequent meetings compared to typical terms.
• Final Exam: Will be proctored using ProctorTrack. Recommended to complete onboarding quiz early.

Engagement and Communication

• Encouraged to ask questions during lectures and reach out via email.
• Emphasizes accessibility and willingness to help students.

Course Outline

Course Schedule

• Classes held Monday to Thursday.
• Office hours before class on Mondays and Thursdays.

Prerequisites

• Must have completed Math 110 and CS 115.
• Familiarity with C++ required but not mandatory to be an expert.

Resources

• Optional textbook: "Data Structures and Algorithms in C++" by Goodrich, Tamassia, and Mount. Not required for course success.
• Course materials are mostly self-contained with notes provided after each class.

Topics Covered

• Abstract Data Types (ADTs)
• Basic computational algorithms
• Introduction to algorithm analysis
• Various data structures including:
  • Lists
  • Stacks
  • Queues
  • Recursion
  • Basics of computational complexity
  • Sorting
  • Hashing
  • Trees

Course Format

• Remote lectures via Zoom with video recordings available afterward.
• Encouragement to take notes during lectures.
• Lecture notes will be posted for accessibility.
• Labs start next week, managed by a separate lab instructor.

Assessment Breakdown

• Final Exam: 60% of final grade.
• Assignments: 3 assignments worth 10% each.
• Lab Work: Worth 10%.
• Assignments will include a mix of written and programming tasks:
  • 1st assignment: Written
  • 2nd assignment: Programming + Written
  • 3rd assignment: Programming
• No midterm exam is scheduled.
• Late assignments not accepted, but submission windows open until 8:30 AM the next morning.

Academic Integrity

• Emphasizes the importance of individual effort on assignments.
• Students may discuss assignments at a high level but should avoid sharing specific implementations.
• Plagiarism detection tools will be used to ensure academic honesty.

Lecture Content Overview

Major Themes in Computer Science

• Emphasis on solving computational problems.
• Data structures and algorithms are the two main components of problem solving in computer science:
  • Data Structures: Systematic organization and access of data.
  • Algorithms: Step-by-step procedures for performing tasks.

Introduction to Data Types

• A data type is a collection of values/objects.
• Can be mathematically specified or given concrete representations in programming languages.

Abstraction in Programming

• Higher-level abstractions allow generalization of problem-solving techniques without getting into specific implementations.
• Abstract Data Types (ADTs) define operations without specifying their implementations.

Stack Abstract Data Type Example

• A stack is a collection that follows Last In, First Out (LIFO) rules.
• Operations:
  • Push: Adds an element to the top of the stack.
  • Pop: Removes and returns the top element of the stack.
  • Other operations may include checking if the stack is empty or getting its size.

Next Steps

• Future lectures will cover implementation details of stacks and various data structures.
• Students encouraged to review the course notes for additional examples and understanding.