3:30-4:50 PM on Tuesdays and Thursdays

**Course Description: **
This course will introduce students to algorithm design, computer programming, and SQL queries. It will provide the fundamental methods, concepts and principles of these topics to give students enough breadth to use these techniques in their jobs and to prepare them to pursue advanced topics in these areas. There will be weekly programming assignments to implement algorithms and SQL covered in the class.

**Prerequisite:** Basic programming skills, algebra and basic calculus, basic real analysis.

**Undergraduate Credit**- Homework (weekly assignments) (35%)
- 2 Midterm exams (12.5% each)
- Final exam (25%)
- Mini Project (15%)
**Graduate Credit**- Homework (weekly assignments) (35%)
- 2 Midterm exams (10% each)
- Final exam (20%)
- Project (25%)

- Algorithm Design: Big O Notation, Growth of Functions, Greedy Algorithms, Divide and Conquer, Dynamic Programming, P/NP and Computational Intractability
- Programming in C++: Variables, Statements, Functions, Pointers, Dynamic Memory Allocation, Libraries, File I/O, etc.
- SQL Queries: Database Design and E/R Model, Relational Model , Basic SQL, Intermediate SQL

There will be roughly 11 homeworks. The lowest homework score will be dropped. A project can have at most 3-4 students. More details in class.

- Algorithm Design by Kleinberg and Tardos. Pearson Education (2013)
- Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. 3rd Edition, MIT Press (2009)
- Database System Concepts by Silberschatz, Korth, and Sudarshan. 6th edition, McGraw-Hill (2010)
- Database Management Systems by Ramakrishnan and Gehrke. 3rd Edition, McGraw-Hill (2002)
- Starting Out with C++ from Control Structures to Objects, 8th Edition, by Tony Gaddis (2014)
**Lectures notes/slides from relevant courses**, e.g., Lecture Slides for Algorithm Design, Introduction to Algorithms, CS225@Illinois- For
**programming in C++**, you may refer to the following tutorials: C++ Tutorial, C++ Lessons, Introduction to C++, C++ reference, learncpp.com

(The lecture slides and recordings will be posted on Compass.)

- Aug 24: Stable Matching
- Chapter 1.1 of Algorithm Design
- Aug 26: C++: Introduction, Control Structures, Conditionals
- Refer to the resources provided above
- Aug 31: Algorithm Analysis: Growth of Functions, Big O Notation
- Chapter 2.1-2.2 of Algorithm Design
- Sep 02: C++: Loops
- Sep 07: Asymptotic Order of Growth, Common Running Time
- Chapters 2.2 of Algorithm Design
- Sep 9: C++: Functions
- Sep 14: Graphs: BFS, Testing Bipartiteness
- Chapters 3.1, 3.2, 3.4 of Algorithm Design
- Sep 16: C++: Arrays, File Operations, Random Numbers
- Sep 21: Greedy Algorithms: Scheduling
- Chapters 4.1-4.2 of Algorithm Design
- Sep 23: C++: Scope, Pointers, Dynamic Memory Allocation
- Sep 28: Greedy Algorithms: Shortest Path, Minimum Spanning Tree
- Chapters 4.4-4.5 of Algorithm Design
- Chapter 14.5 of Introduction of Algorithms
- Sep 30: C++: Implementation of Stable Matching
- Oct 05: Review Class
- Oct 07: C++: Data Structures and Implementation of Graph Algorithms
- Oct 12:
**Midterm 1** - Oct 14: Database Design and Relational Model
- Oct 19: Greedy Algorithms
- Oct 21: Intro to SQL
- Oct 26: Dynamic Programming Paradigm
- Chapter 15.1 of Introduction to Algorithms
- Oct 28: SQL
- Nov 02: Dynamic Programming: Knapsack
- Chapters 6.1-6.2, 6.4 of Algorithm Design
- Nov 04: SQL
- Nov 09: Database Design: Entity-Relationship Model
- Nov 11:
**Midterm 2** - Nov 16: Divide and Conquer Paradigm: Recurrence Relation, MergeSort, Integer Multiplication, Binary Search
- Chapter 5.1, 5.2, 5.5 of Algorithm Design
- Nov 18: SQL
~~Nov 23:~~Fall Break~~Nov 25:~~Fall Break- Nov 30: NP and Computational Intractability, NP-complete Problems
- Chapter 8.1, 8.2, 8.4 of Algorithm Design
- Dec 02: SQL
- Dec 07: Review Class
- Dec 10-13:
**Project Submission and Demo** - Dec 15:
**Final Exam (1:30-4:30 PM)**