Diferență între revizuiri ale paginii „Data Structures and Algorithms”

De la WikiLabs
Jump to navigationJump to search
 
(Nu s-au afișat 43 de versiuni intermediare efectuate de alți 2 utilizatori)
Linia 9: Linia 9:
 
* Lecture 5: [[Fișier:lecture5.pdf]]
 
* Lecture 5: [[Fișier:lecture5.pdf]]
 
* Lecture 6: [[Fișier:lecture6.pdf]]
 
* Lecture 6: [[Fișier:lecture6.pdf]]
* Lecture 7: [[Fișier:lecture7.pdf]]
+
* Lecture 7: Examples: [[list.h]] [[list.c]] [[test_list.c]]
 
* Lecture 8: [[Fișier:lecture8.pdf]]
 
* Lecture 8: [[Fișier:lecture8.pdf]]
 
* Lecture 9: [[Fișier:lecture9.pdf]]
 
* Lecture 9: [[Fișier:lecture9.pdf]]
Linia 15: Linia 15:
 
* Lecture 11: [[Fișier:lecture11.pdf]]
 
* Lecture 11: [[Fișier:lecture11.pdf]]
 
* Lecture 12: [[Fișier:lecture12.pdf]]
 
* Lecture 12: [[Fișier:lecture12.pdf]]
* Lecture 13: [[Fișier:lecture13.pdf]]
 
* Lecture 14: [[Fișier:lecture14.pdf]]
 
  
 
== Homework - 2014 ==
 
== Homework - 2014 ==
  
# [[DSA Homework 1]] - soft deadline: 13.03.2014, 23:59, hard deadline: 27.03.2014, 23:59
+
# [[DSA Homework 1]] - soft deadline: 13.03.2014, 23:59, hard deadline: 27.03.2014, 23:59 - [https://docs.google.com/spreadsheets/d/17_iF5S8TjUS96Y_3fnfiJgX71Ly0joPqRG3pGKdAFKo/edit?usp=sharing Results]
# [[DSA Homework 2]] - soft deadline: 27.03.2014, 23:59, hard deadline: 10.04.2014, 23:59
+
# [[DSA Homework 2]] - soft deadline: 27.03.2014, 23:59, hard deadline: 10.04.2014, 23:59 - [https://docs.google.com/spreadsheets/d/17_iF5S8TjUS96Y_3fnfiJgX71Ly0joPqRG3pGKdAFKo/edit#gid=1273316209 Results]
 +
# [[DSA Homework 3]] - soft deadline: 10.04.2014, 23:59, hard deadline: 24.04.2014, 23:59 - [https://docs.google.com/spreadsheets/d/17_iF5S8TjUS96Y_3fnfiJgX71Ly0joPqRG3pGKdAFKo/edit#gid=1321731689 Results]
 +
# [[DSA Homework 4]] - soft deadline: 24.04.2014, 23:59, hard deadline: 08.05.2014, 23:59 - [https://docs.google.com/spreadsheets/d/17_iF5S8TjUS96Y_3fnfiJgX71Ly0joPqRG3pGKdAFKo/edit#gid=1950506581 Results]
 +
# [[DSA Homework 5]] - soft deadline: 08.05.2014, 23:59, hard deadline: 22.05.2014, 23:59 - [https://docs.google.com/spreadsheets/d/17_iF5S8TjUS96Y_3fnfiJgX71Ly0joPqRG3pGKdAFKo/edit#gid=283577219 Results]
 +
# [[DSA Homework 6]] - hard deadline: 22.05.2014, 23:59 - [https://docs.google.com/spreadsheets/d/17_iF5S8TjUS96Y_3fnfiJgX71Ly0joPqRG3pGKdAFKo/edit#gid=1238235853 Results]
  
 
Homework submitted after the '''soft deadline''' will only receive half the credit. Homework submitted after the '''hard deadline''' will receive no credit.
 
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 [https://www.coursera.org/course/pythonlearn 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 [https://www.coursera.org/course/algs4partI algorithm course] on Coursera staring on 13th of June.
  
 
=== Deliverables ===
 
=== Deliverables ===
Linia 37: Linia 43:
 
The e-mail '''body''' should contain any comments you wish to make on the homework.
 
The e-mail '''body''' should contain any comments you wish to make on the homework.
  
The e-mail '''attachments''' should consist of two files: the C source file, having a .c extension, and a text file, having a .txt extension, containing the algorithm description and analysis.
+
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.
 
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).
 +
 +
* Where: [[Data Structures and Algorithms (lab)]]
  
 
== Useful Links ==
 
== Useful Links ==
  
 
* Coding conventions: [[C Coding Conventions]]
 
* Coding conventions: [[C Coding Conventions]]
* Virtual machine: [ftp://zeus.arh.pub.ro/pub/VirtualMachines/ LinuxDev]
+
* Virtual machine: [ftp://hermes.arh.pub.ro/public/VirtualMachines/ LinuxDev]
 
* Linux Command Line tutorial for beginners: http://linuxcommand.org/learning_the_shell.php
 
* Linux Command Line tutorial for beginners: http://linuxcommand.org/learning_the_shell.php
 
* PDF algorithm reference book: [https://drive.google.com/file/d/0B0KC3c5boTpYLXY4UE9qUWJaTHM/edit?usp=sharing Cormen]
 
* PDF algorithm reference book: [https://drive.google.com/file/d/0B0KC3c5boTpYLXY4UE9qUWJaTHM/edit?usp=sharing Cormen]
Linia 55: Linia 74:
 
* The Art of Computer Programming: [http://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043/ref=sr_1_1?s=books&ie=UTF8&qid=1395001210&sr=1-1&keywords=knuth Knuth]
 
* The Art of Computer Programming: [http://www.amazon.com/Computer-Programming-Volumes-1-4A-Boxed/dp/0321751043/ref=sr_1_1?s=books&ie=UTF8&qid=1395001210&sr=1-1&keywords=knuth Knuth]
 
* Concrete Mathematics: A Foundation for Computer Science: [http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025/ref=sr_1_1?s=books&ie=UTF8&qid=1395001255&sr=1-1&keywords=concrete+mathematics Knuth]
 
* Concrete Mathematics: A Foundation for Computer Science: [http://www.amazon.com/Concrete-Mathematics-Foundation-Computer-Science/dp/0201558025/ref=sr_1_1?s=books&ie=UTF8&qid=1395001255&sr=1-1&keywords=concrete+mathematics Knuth]
 +
 +
== Other resources ==
 +
 +
* Algorithms: Design and Analysis, Part 1: [https://www.coursera.org/course/algo here]
 +
* Algorithms: Design and Analysis, Part 2: [https://www.coursera.org/course/algo2 here]
 +
* Analysis of Algorithms: [https://www.coursera.org/course/aofa here]
 +
* Algorithms, Part I: [https://www.coursera.org/course/algs4partI here]
 +
* Algorithms, Part II: [https://www.coursera.org/course/algs4partII here]
 +
* Stack Overflow: [http://stackoverflow.com/questions/tagged/c here]
 +
 +
== Exam ==
 +
 +
These are [https://docs.google.com/spreadsheets/d/1uaqm6xi_jJrzrMOneNJUsN0Qi5Fn9SeHiOPqD1aR-uw/edit?usp=sharing final DSA grades] for 2013-2014.
 +
 +
'''Note''': Student with 49 points and above will be scheduled for interviews. They will be added early this week.
 +
 +
'''Note''': Please make sure you fill in the [https://docs.google.com/forms/d/161DHb_mk4q4o7p4irKktyBHBu4ZiKoyrJXhMlsM0oSs/viewform subject evaluation form] before the end of the exams session.
 +
 +
* The interviews for the homework for students that obtained 49p+ 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.
 +
 +
== Second Evaluation Session - September ==
 +
 +
The rules for the September re-evaluation are as follow:
 +
 +
* The final grade will be the sum of two grades:
 +
** The grade for the continuous evaluation (lab + homework) throughout the semester - 80 points
 +
** The grade for the final exam (multiple choice questions + application) - 30 points
 +
 +
* In order to increase the continuous evaluation grade, you may implements one of the listed [[DSA Projects]] and present it during the exam session in September. Keep in mind that this grade will overwrite the one you have received during the semester. You may also choose to keep the grade you already have, if you consider it is enough for you to pass the subject. The presentations for any implemented projects will be done publicly, so you are also required to create 3-4 slides and talk about the code you wrote.
 +
 +
* The grading for the final exam will be identical to the examination that took place in June.
 +
 +
<font color="red">'''Update:'''</font> The autumn session exams are scheduled on the 12th and 14th of September, at 10:00 AM, in A410. The supervisors will be Gabriel Neagoe on the 12th and Radu Hobincu on the 14th.
 +
 +
<font color="red">'''Update:'''</font> [https://docs.google.com/spreadsheets/d/1G4lDfD5S79Vr59iCdua4Bc65d17UHDhZYYN0HLo-8tw/edit?usp=sharing These] are the DSA grades for 2013-2014 second evaluation session.

Versiunea curentă din 16 noiembrie 2015 16:46

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

Homework - 2014

  1. DSA Homework 1 - soft deadline: 13.03.2014, 23:59, hard deadline: 27.03.2014, 23:59 - Results
  2. DSA Homework 2 - soft deadline: 27.03.2014, 23:59, hard deadline: 10.04.2014, 23:59 - Results
  3. DSA Homework 3 - soft deadline: 10.04.2014, 23:59, hard deadline: 24.04.2014, 23:59 - Results
  4. DSA Homework 4 - soft deadline: 24.04.2014, 23:59, hard deadline: 08.05.2014, 23:59 - Results
  5. DSA Homework 5 - soft deadline: 08.05.2014, 23:59, hard deadline: 22.05.2014, 23:59 - Results
  6. DSA Homework 6 - hard deadline: 22.05.2014, 23:59 - Results

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

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

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

These are final DSA grades for 2013-2014.

Note: Student with 49 points and above will be scheduled for interviews. They will be added early this week.

Note: Please make sure you fill in the subject evaluation form before the end of the exams session.

  • The interviews for the homework for students that obtained 49p+ 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.

Second Evaluation Session - September

The rules for the September re-evaluation are as follow:

  • The final grade will be the sum of two grades:
    • The grade for the continuous evaluation (lab + homework) throughout the semester - 80 points
    • The grade for the final exam (multiple choice questions + application) - 30 points
  • In order to increase the continuous evaluation grade, you may implements one of the listed DSA Projects and present it during the exam session in September. Keep in mind that this grade will overwrite the one you have received during the semester. You may also choose to keep the grade you already have, if you consider it is enough for you to pass the subject. The presentations for any implemented projects will be done publicly, so you are also required to create 3-4 slides and talk about the code you wrote.
  • The grading for the final exam will be identical to the examination that took place in June.

Update: The autumn session exams are scheduled on the 12th and 14th of September, at 10:00 AM, in A410. The supervisors will be Gabriel Neagoe on the 12th and Radu Hobincu on the 14th.

Update: These are the DSA grades for 2013-2014 second evaluation session.