Data Structures and Algorithms
The Data Structures and Algorithms course is based on knowledge gained from the Computer Programming course in the first semester, and its role is to provide the base for algorithmic thinking, problem solving and advanced computer programming skills.
Lecture Slides
- Lecture 1: Fișier:Lecture1.pdf
- Lecture 2: Fișier:Lecture2.pdf
- Lecture 3: Fișier:Lecture3.pdf
- Lecture 4: Fișier:Lecture4.pdf
- Lecture 5: Fișier:Lecture5.pdf
- Lecture 6: Fișier:Lecture6.pdf
- Lecture 7: Examples: list.h list.c test_list.c
- Lecture 8: Fișier:Lecture8.pdf
- Lecture 9: Fișier:Lecture9.pdf
- Lecture 10: Fișier:Lecture10.pdf
- Lecture 11: Fișier:Lecture11.pdf
- Lecture 12: Fișier:Lecture12.pdf
Homework - 2014
- DSA Homework 1 - soft deadline: 13.03.2014, 23:59, hard deadline: 27.03.2014, 23:59 - Results
- DSA Homework 2 - soft deadline: 27.03.2014, 23:59, hard deadline: 10.04.2014, 23:59 - Results
- DSA Homework 3 - soft deadline: 10.04.2014, 23:59, hard deadline: 24.04.2014, 23:59 - Results
- DSA Homework 4 - soft deadline: 24.04.2014, 23:59, hard deadline: 08.05.2014, 23:59 - Results
- DSA Homework 5 - soft deadline: 08.05.2014, 23:59, hard deadline: 22.05.2014, 23:59
- DSA Homework 6 - hard deadline: 22.05.2014, 23:59
Homework submitted after the soft deadline will only receive half the credit. Homework submitted after the hard deadline will receive no credit.
Information: There is a general programming course starting on Coursera on the 2nd of June. I recommend taking it in order for you to practice concepts and learn a new programming language. Python is widely spread and really useful for you to know.
Information: There is an algorithm course on Coursera staring on 13th of June.
Deliverables
Submissions must include one or more C source files, compilable with GCC version 4.8.0 or greater, and a .txt document (NOT a doc/ docx or pdf file) including the algorithm description and a short analysis of the complexity.
Submission
Homework will be submitted via e-mail at address homework@dcae.pub.ro.
The e-mail subject MUST follow the following template: [DSA]<your_name> - <your_group> - <homework #>. E.g.: [DSA]Radu Hobincu - 421G - 1
The e-mail body should contain any comments you wish to make on the homework.
The e-mail attachments should consist of at least two files: one or more C source files, having a .c extension, and a text file, having a .txt extension, containing the algorithm description and analysis.
NOTE: The arrival time of the e-mail is considered as the submission time, so make sure you submit some time before the deadline.
Code Examples
- Read & Write strings from/ to a file: file_test.c
- Stack: stack.h stack.c
- Connected graph example: connected_graph.c matrix.in
- Prim's Algorithm: prim.c
DSA Lab Web Page
On this web page you will find lab assignments, code examples, related resources and, as a bonus, you can evaluate your progress (how many points you have obtained so far).
Useful Links
- Coding conventions: C Coding Conventions
- Virtual machine: LinuxDev
- Linux Command Line tutorial for beginners: http://linuxcommand.org/learning_the_shell.php
- PDF algorithm reference book: Cormen
Recommended readings
- The Algorithm Design Manual: Skiena
- Algorithms (4th Edition): Sedgewick & Wayne
- An Introduction to the Analysis of Algorithms: Sedgewick
- The Art of Computer Programming: Knuth
- Concrete Mathematics: A Foundation for Computer Science: Knuth
Other resources
- Algorithms: Design and Analysis, Part 1: here
- Algorithms: Design and Analysis, Part 2: here
- Analysis of Algorithms: here
- Algorithms, Part I: here
- Algorithms, Part II: here
- Stack Overflow: here
Exam
- The interviews for the homework for students that obtained 50p+ is on the 1st of June at 10:00 DSA - Interview Schedule
- DSA - Exam schedule
- The maximum points for the final exam are 30 points split into 15p a multiple choice test for 15 mins and 15p for a practical application.
