DSA-lab

Data Structures and Algorithms lab repository

Structure

Lab 1: Introduction to GIT and the work-flow of the lab + starting with Singly Linked Lists

• Assignments 1:
  • 1.1 Basic Operations on a Singly Linked List
  • 1.2 Wanted: Jim Kong-nu (extra credit!)

Lab 2: Circular Linked Lists and Doubly Linked Lists (+ Introduction to complexity)

• Assignments 2:
  • 2.1 Basic Operations on Doubly Linked Lists with Santinel
  • 2.2 Queue (or qwewe)

Lab 3: Test 1 - Lists

• Statistics - [problems, some good solutions and grades distributions] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Tests/T1%20-%20Lists)

Lab 4: Trees - more precisely, Binary Trees, Balanced Binary Trees (the theory)

• Assignments 3:
  • 3.1 [Trees to list and back again] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%203/Assignment%203%20-%20Tree%20to%20list%20and%20back%20again)
  • 3.2 [Parse trees] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%203/Assignment%203%20-%20extra%20credit%20(parse%20tree)) (extra credit!)

Lab 5: Binary Search Trees

• Assignments 4:
  • 4.1 [Insertion in a AVL (Perfectly Balanced BST)] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%204/Assignment%204%20-%20Insertion%20in%20AVL%20Trees%20(Perfectly%20Balanced%20BST))
  • 4.2 [Deletion in an AVL (Perfectly Balanced BST)] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%204/Assignment%204%20-%20Deletion%20in%20AVL%20Trees%20(extra%20credit)) (extra credit!)

Lab 6: Test 2 - Trees

• Statistics - [problems, almost minimal solutions and grades distributions] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Tests/T2%20-%20Trees)

Lab 7: Graphs - representation and traversals

• Assignments 5:
  • 5.1 [Adjacency List] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%205/Assignment%205.1%20-%20Adjacency%20List)
  • 5.2 [Longest Simple Path] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%205/Assignment%205.2%20-%20Longest%20Simple%20Path%20-%20extra%20credit) (extra credit!)

Lab 8: Graphs - Graph Processing Algorithms (Dijkstra, Prim, Kursal, Floyd etc.)

• Assignments 6:
  • 6.1 [Kruskal and Bellman Ford] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%206/Assignment%206.1%20-%20Kruskal%20and%20Bellman%20Ford)
  • 6.2 [Vertex Cover Approximation] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%206/Assignment%206.2%20-%20Vertex%20Cover%20Approximation%20-%20extra%20credit) (extra credit!)

Lab 9: Test 3 - Graphs

• [Test Skeleton project] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Interesting%20Stuff/Graphs101%20-%20test%20skeleton)
• Statistics - [complete solutions to all algorithms and grades distributions] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Tests/T3%20-%20Graphs)

Lab 10: Hash Tables - introduction, collision detection, usages

• Assignments 7:
  • [Meta-instructions] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%207)
  • [Hash Tables - Open Addressing] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%207/Assignment%207.1%20-%20Hash%20Tables%20-%20Open%20Addressing)
  • [Hash Tables - Chaining] (https://github.com/AC-2015-Sem2/DSA-lab/tree/master/Assignments/Assignment%207/Assignment%207.2%20-%20Hash%20Tables%20-%20Chaining)

Lab 11: Sorting Algorithms - Bubble, Insertion, Selection, Merge, Quick, Radix.

• Assignments 8: TBA

Lab 12: Test 4 - Sorting Algorithms & Hash Tables

• Assignments: none

Lab 13: Exam problem practice

• Assignments: none

Grading

• Assignments = 10% of total lab grade (each graded individually and separately, no 'collective' assignments)
• Test 1 - 20%
• Test 2 - 25%
• Test 3 - 25%
• Test 4 - 20%

Administrative

• Max number of absences = 1 (NOT applicable for test days - if you miss a test day, you'll have to take the test separately, problem will be more difficult)
• Assignments will be given dynamic feedback through GIT and will be graded only after one says he/she is thoroughly done with it.
• Only assignments which are pushed to GIT will be graded and taken into consideration.
• "Extra credit" assignments can only be completed by those who already have completed the 'normal' assignments. They will be even more thoroughly inspected and evaluated.

About tests

• Grades range: 1-10
• Code does not even compile: 1 (by default, no excuses)
• For every warning: -0.25 on the grade - your code should be clean enough to surpass any Codeblocks warnings
• Cheating attempts: 1 (by default, no excuses)
• Work will be copied to USB stick and will be graded in maximum 48 hours
• Results on GIT - check grades.xls file in every group folder

GIT Tutorials

• 1 - Installing GIT
• 2 - Fork and Clone
• 3 - Commit Push and Pull Request

Interesting Stuff

• Generic Lists more exactly, how to create a (reusable) node which can remain the same for most of the functionality of the list regardless of the problem to be solved?
• Pointers to functions a cute example of how you can use a structure to simulate OOP behaviour.

Catalysts Coding Contest

• Anyone who chooses to participate in the Catalysts Coding Contest (<-- LINK) will be awarded 0.3 points to the final mark
• For every level successfully completed (with or without a team) an additional 0.1 points will be added to everyone in the team (or to the solo participant) up to a total of 0.7 points if you somehow manage to complete all 7 levels
• If you manage to be in the top 10 contestants you will get an additional 1 point to the final grade
• Don't forget - free pizza and drinks at the end!
• Helpful hint #1: the first two levels are terribly simple most of the times
• Helpful hint #2: you sample a few problems here (<-- LINK)