Data Structures and Algorithms I (2023)
In this course, we will see how to structure data (data structures) so that complex operations (algorithms) can be efficiently executed. This course lies in the intersection of mathematics and computing. We will learn about the most basic and widely-used data structures and algorithms, prove their correctness and efficiency by writing mathematics, and implement them using C/C++ to understand how they work in practice.
Administrivia
If you are absent from a lecture until Exam I for any reason, fill the form of absence for ES242.
Fill this form to select your availability for labs.
Meetings
Nov 15
Binary search trees. Definition. Search. Running-time. Discussion on proof approaches to worst-case upper bounds and lower bounds.
Nov 13
Rehashing. Amortized analysis of insertion.
Application of linked lists: window switching.
Nov 8
Implementing hash tables.
Nov 6
Hash tables for implementing Python dictionaries.
Nov 1
Implementing stacks and queues using linked lists, tail-sharing, circular singly linked lists.
Oct 23
Linked lists. Allocation and insertion.
Oct 18
Discussion on exam 2 solutions.
Oct 9
BFS implementation for solving 8-puzzles with the minimum number of moves.
Oct 4
Queues, BFS, finding solutions to puzzles in the smallest number of steps.
Sep 27
Sudoku solving and DFS time complexity analysis.
Sep 25
DFS for path-finding and writing a sudoku solver.
Sep 20
Stacks and implementation of an RPN calculator.
Sep 18
DFS and depth-first search trees. The tictactoe algorithm is a DFS.
Sep 13
Encoding and decoding tictactoe strategy into bytes. Indexing boards.
Sep 11
4x4 tic-tac-toe. Memoization. Fibonacci numbers with memoization.
Sep 2
Exam I
Aug 30
Fixing bug in tictactoe. Use of void * in C.
Aug 28
Implementing optimal tictactoe strategy using recursion.
Aug 23
Proof of correctness for permutations. Accepting function pointers for generality.
Aug 21
Recursion: Towers of Hanoi, Generating all permutations.
Aug 17
Demo and support on setting up C, Git, Zulip by Reuben.
Aug 16
gcdlcm function, definition of asymptotic primitives.
Aug 14
Loop invariants, Time complexity of Euclid’s algorithm.
Design of gcdlcm function and multiple return values.
Aug 10
Tutorial 1.
Aug 9
Euclid’s GCD algorithm. Termination. Correctness (GCD Theorem). Direct proofs. Proof by induction.
Aug 7
Discussion on gcd. Computers vs unit-cost RAM. Execution trace and running time.
Aug 3
Discussion on specification of computational problems. Algorithms. Naive GCD computation.
Aug 2
General introduction to the course, policies, administrative stuff.
Attendance in a lecture until exam I will earn you 1 mark provided you attempt the live quiz and score sixty percent or above. If you attend the live quiz and score less than sixty percent, you are required to attempt until you score sixty or above. If you miss a lecture for a valid reason, you can attend the quiz at a later time and receive the marks for attendance.
Grading
| Assessment | Percentage |
|---|---|
| Attendance | 10 |
| Lab Assignments | 20 |
| Exam I | 20 |
| Exam II | 20 |
| Exam III | 30 |
Lecture Plan
| #Lectures | Topic |
|---|---|
| 1 | Problems, Algorithms |
| 1 | Execution, Time |
| 2 | Asymptotic Analysis |
| 2 | Proofs |
| 2 | Recursion |
| 2 | Stacks |
| 1 | Queues |
| 1 | Priority queues |
| 1 | Heaps, heapsort |
| 2 | Sets, Dictionaries |
| 1 | Dynamic arrays |
| 2 | Hashing |
| 2 | Binary Search Trees |
| 3 | Graphs, Trees |
| 2 | Traversal |
| 2 | Graph algorithms |
| 3 | Reductions |