Algorithms and Data Structures - 1

CS 0445, Fall 2023

This is an introduction to the design and implementation of data structures (linked lists, stacks, queues, hash tables) and related algorithmic techniques (searching, sorting, recursion). We examine these ideas in the context of an object-oriented language, namely Java.

Students are expected to complete a number of programming projects illustrating the concepts presented.

Below you will find the materials related to the course arranged according to the timeline. For up-to-date course announcements and information please refer to the canvas course page.

Calendar

Week 1	Aug 28	Introduction and Setup. Motivation. Goals. Course mechanics. Slides-intro. DEMO Role of data structures: LINK.
		Java: review. Encapsulation. Data hiding. Abstraction. Reference variables. Slides 1. DEMO Reference variable gotchas: LINK. READ Readings and quizzes: Week 1.
Week 2	Sep 4	Reusing Java classes: Composition. Mutable and immutable objects. Copying objects: shallow and deep copy. Slides 2. DEMO Deep and shallow copy: LINK.
		Reusing Java classes: Inheritance . Polymorphism. Abstract classes. Interfaces. Slides 3. DEMO Interfaces and polymorphism in Animal simulation program: LINK. READ Readings and quizzes: Week 2. TASK Recitation 1: Copying Objects. Link.
Week 3	Sep 11	Java Generics . Parametrized Data Types. Wildcard types. Slides 4. DEMO Generic arrays: LINK. DEMO Generic sorting. LINK. TASK Recitation 2: Subclassing Sequences. Link.
		Abstract Data Types (ADT) . Definition of ADT. ADT vs. Data Structures. Queue ADT. Queue implementation using a circular array. Slides 5. READ Readings and quizzes: Week 3. TASK + Programming Assignment 1: Shufflable Queues. Link.
Week 4	Sep 18	Introduction to Algorithms. Algorithm design basics. Pseudocode. Basic instructions. RAM model of computation. Slides 6.
		Algorithm Analysis. Bounding functions. Rate of growth. Big O. Slides 7. Classes of Algorithms. Linear search and Binary search. Simple searching algorithms. Slides 8. READ Readings and quizzes: Week 4. TASK Recitation 3: Running time of algorithms. Link.
Week 5	Sep 25	Basic Data Structures. Arrays and Linked Lists. Complexity of operations on Arrays and Linked Lists. Dynamic (resizable) arrays. Slides 9.
		Stack and Queue ADT. Specifications. Implementing Stack and Queue using Arrays and using Linked Lists. Slides 10. READ Readings and quizzes: Week 5. TASK Recitation 4: Linked Lists. Link.
Week 6	Oct 2	List ADT. Specifications. Implementing List with Arrays and Linked Lists. Doubly-linked lists. Slides 11.
		Iterators. Motivation. Iterator interface. Implementing iterators for List ADT. Slides 12. DEMO Iterators vs. get entry: LINK. READ Readings and quizzes: Week 6. TASK Recitation 5: Testing and Debugging. Link. TASK + Programming Assignment 2: Stack, Queue and Mazes. Link.
Week 7	Oct 9	Map and Set ADT. Specifications. Efficient implementation using Hash Tables. Hashing Functions. Slides 13.
		Exam 1 review. Answering your questions about Exam 1 topics. Review Slides. TASK Recitation 6: Linked Lists Practice. Link. TASK Big O practice. Link.
Week 8	Oct 16	Exam 1. Topics: LINK.
		Hash Tables. Collision resolution techniques. Slides 14. READ Readings and quizzes (from the last week): Week 7. TASK Recitation 7: Java HashMap with custom keys. Link.
Week 9	Oct 23	Recursion. Introduction to recursive algorithms. Estimating running time with Recursion tree. Recursive data structures. Recursion vs. Iteration. Tail recursion. Slides 15. DEMORecursive sequential search in Arrays and Linked Lists LINK.
		Divide and Conquer. Recursive Binary Search. Power function. Slides 16. DEMOBinary search. Power function. LINK. READ Readings and quizzes: Week 9. TASK Recitation 8: My HashMap. Part I of Assignment 3. Link.
Week 10	Oct 30	Sorting algorithms (1/3). Introduction to sorting. Simple sorting algorithms. Slides 17. Sorting with divide-and-conquer. Recursive Merge Sort. Slides 18. DEMO Sorting in Java with Comparable and Comparators. LINK.
		Sorting algorithms (2/3). Lower-bound on comparison-based sorting. Non-comparison-based sorting algorithms: Count Sort. Radix Sort. Slides 19. READ Readings: Week 10. TASK Recitation 9: Recursive challenge. Link. TASK + Programming Assignment 3: Hashing Books. Link.
Week 11	Nov 6	Sorting algorithms (3/3). Quicksort. Randomized Quicksort. Slides 20. Video. DEMO Simple implementations of sorting algorithms. LINK.
		Recursion optimizations. Memoization. Backtracking. Slides 21. Video. DEMO Backtracking examples: n-Queens and Maze search. LINK. READ Readings and quizzes: Week 11. TASK Recitation 10: Binary-search challenge. Link.
Week 12	Nov 13	Pattern Matching algorithms (1/2). Brute force substring search. Linear-time algorithm by Knuth-Morris-Pratt (KMP). Slides 22. DEMO Shifting heuristics visualizer. LINK.
		Pattern Matching algorithms (2/2). . Boyer-Moore algorithm. Rabin Karp algorithm. Slides 23. READ Readings and quizzes: Week 12. Readings are from this book chapter: LINK. DEMO Simplified implementations of string searching algorithms. LINK. TASK + Programming Assignment 4: Boggle solver. Link.
Week 14	Nov 27	Review for Exam 2. Sorting algorithms. Tail recursion. Memoization. Slides.