Data Structures and Algorithms (NYU Paris, Spring 2021)
The design and analysis of efficient data structures is a vital subject in computing and is part of the curriculum of every computer science and computer engineering student. In this course, we will learn how to model computational problems. We will cover the most important algorithms, algorithmic paradigms and data structures used to solve those problems. We will discuss efficiency and scalability.
More specifically, the course will cover topics such as object oriented programming, as well as Sorting and Trees, Hashing, Number theoretic algorithms including RSA encryption, Graphs and Shortest paths and the notion of NP-Completeness.
The students will get the opportunity to program the algorithms that are discussed during the lectures in Java.
The class will follow the structure
1. Lectures (introduction of the new material that will be needed during the lab sessions and for the assignments)
2. Programming (lab) sessions, (you have the opportunity to apply what you have learned during the lecture, and you can ask all the questions you want to make sure you understand everything before the assignement)
3. Assignments (You are given a new problem and you are evaluated on your ability to use the course material to solve this new problem)
Schedule and Classroom
Lecture: Tuesday/Thursday, 12.30pm – 1.45pm (Paris time), Room 410
Recitations: Tuesday 2.15pm – 3.45pm (Paris time). Room 410
Office hour: Thursday 2.15pm – 3.45pm (Paris time)
Except if explicitely stated otherwise, assignments are due at the beginning of each class.
Current (temporary) version of the notes: Lecture notes
Practice (theory) Questions for each exam can be found by clicking on those exams below
Exam : 60% of the grade (30% midterm, 30% final)
Assignments : 30 % of the grade (Tentative schedule below)
Final Project : 10 % of the grade (Tentative schedule below)
The Github page for the class will be hosted at https://github.com/acosse/DataStructures2021 and will be used for the lab and the assignments. You can also click on each “Lab” in the schedule below and this will re-direct you to the github page.
Legend: Lab sessions are in green, Homeworks are in red (right side of the table), dates related to the project are in orange.
|Week 1||01/26, 01/28||Reminders/Intro to Java, Elementary programming
including loops, strings, arrays, objects, classes,… Lab 1 (Setting up Java, git,..)
|Week 2||02/02, 02/04||Object Oriented Programming and Design, Part I,
Slides, Solution Ex1.1., Solution Ex1.2., Solution Ex1.3.
| Assign. 1
|Week 3||02/09, 02/11||
Object Oriented Programming and Design Part II
including inheritance and Abstract classes, Lab 3
Slides Inheritance, Slides arrays , Solutions Exercise 1.1 and 1.3
| Assign. 1 due,
|Week 4||02/16, 02/18||Fundamental data structures
Multidimensional arrays, Linked Lists,
Numerics, integers, RSA encryption, Slides, Lab 4
Solution Ex. 1.1, Ex. 1.7 (with Object)
||Algorithm analysis including Asymptotic Analysis and the “Big Oh” notation |
Slides, Lab 5, Solutions exercises 1.1, 1.4 and 1.10
||Stacks, Queues and Deques
(Possibly List ADT),
||Trees Part I including general and Binary Trees,
Tree Traversal algorithms,.. Slides Part I , Slides Part II, Lab 7, Solutions
||Trees Part II (including Search Trees, Balanced Search Trees)
Slides 1, Slides 2 , Slides 3, Lab 8
||Priority queues, Heaps, Maps, Hash Tables
Slides Priority Queues,
Slides Hash Table (Part II), Lab 10
||Sorting Part I, Lab 11
||Sorting part II, Lab 12
||Graph Algorithms including BFS, DFS, topological Sort,
Min Spanning trees, Max Flow,.. Lab 13
||Advanced Topics including Dynamic Programming, Linear Programming,
Approximation and Randomized Algorithms,…
||Revisions (link to Lab) Element iterator demo, Position iterator demo
- Data structures and algorithms in Java, Goodrich, Tamassia, Goldwasser
- A Java Reference: Assorted Java Reference Material, Paul N. Hilfinger, UCB
- The Java Language Specification (Java SE 14 Edition) by James Gosling, Bill Joy, Guy Steele, Gilad Bracha, Alex Buckley, and Daniel Smith
- Introduction to Java programming and data structures, Y. Daniel Liang.
- See also
Lab Sessions and programming policy
The lab sessions will require you to do some programming.
Downloading and getting started with Java.