Transcript Student Projects in the Course Data Structures

Student Projects in the Course
Data Structures
Hristina Mihajloska
Outline
• About the course Data Structures
• Student Projects in Java
• Gains and Conclusion
About the course Data Structures
• Big team for a large number of students 
▫ Lectures
 Ana Madevska-Bogdanova
 Anastas Mishev
▫ Auditory exercises
 Boro Jakimovski
 Magdalena Kostoska
▫ Laboratory exercises
 Hristina Mihajloska
 Panche Ribarski
About the course Data Structures
• Weekly schedule:
▫ 2 hours – lectures
▫ 3 hours – auditory exercises
▫ 3 hours – laboratory exercises (in computer
laboratory)
• Practice:
▫ laboratory groups up to 20 students
• Projects:
▫ two compulsorily practical single-handed projects
Assumed Background
• Student has taken the course Object-oriented
Programming
• Knowledgeable about
▫ Java language basics
▫ Object-oriented design
▫ Recursion
Grading Information
•
•
•
•
•
Two theory exams: 30%
Two practical exams: 30%
Assignments: 20%
Projects: 20%
Class participation: 5% (bonus)
Course Objectives
• Learning some of the common data structures
• Different ways for their implementation
• Ability for analyzing the complexity of
algorithms which use data structures
• Using data structures for solving practical
problems
Course Topics
•
•
•
•
•
•
•
•
•
Algorithm complexity
Fundamental Data Structures
Abstract Data Types
Stacks and Queues
Hash Tables
Trees
Priority queues and Heaps
Sorting
Search trees
Course Difficulties
• Student perspective
▫ practical exams much harder then weekly
assignments
Course Difficulties
• Teacher perspective
▫ few of the students could pass practical exams
• Solution
▫ Implementing single-handed student
project one week before every practical
exam (during course semester)
Student Projects
• Goals
▫ good preparation for practical exam
▫ to improve analytical reasoning and programming
skills
▫ to distinguish which data structure to be used in
practical problem
Student Projects
• For every project exists three levels of
complexity which are graded differently
• Students are asked to choose one of them and
find a solution in given time
▫ no points for programs that do not compile
Student Projects
• First level (easiest)
▫ Identification of the data structure in the practical
problem
▫ It is obvious
• Second level (middle)
▫ Students have to combine two data structures to
solve the problem
• Third level (hardest)
▫ To build a new data structure which is combination of data
structures covered by the material
▫ To implement it in a different way
Examples
• Third-level project
▫ Write an implementation for data structure Bag as a
Java class, which is similar to a set, but it may contain
several instances of the same member. For example,
{'to', 'be', 'or', 'not', 'to', 'be'} is a bag of words, which is
equal to {'be', 'be', 'not', 'or', 'to', 'to'} (since order of
members is insignificant), but is unequal to {'be', 'not',
'or', 'to'} (since the number of instances is significant).
Adding (removing) a member increases (decreases)
the number of instances in the bag by one. The
member is deleted from the bag when it has no
instances . . .
Examples
• Third-level project . . .
▫ Design a bag ADT. Provide set-like operations,
including bag union and bag subsumption (but
not bag intersection or difference). In addition,
provide an operation that returns the number of
instances of a given member.
▫ How would you represent a bag without actually
storing multiple instances of the same member?
▫ Implement a bag ADT using a sorted array
▫ Implement a bag ADT using a sorted SLL
Examples
• Middle-level project
▫ One arithmetic expression is given within an xml
file. Process this xml file and put it in an adequate
structure. The structure should enable evaluation
of the expression. For a given xml file find the
value of the expression.
...
Student Projects
• Gains
▫ increased the number of students that passed
practical exams
▫ conceptual and concrete ways to organize data for
efficient storage and efficient manipulation
▫ make use of data structures in the design of
efficient algorithms
Conclusion
• We got good programming solutions for the
given problems
• Good students like this way of teaching
• If students did their projects alone, they are well
prepared for practical exams
Thank you for your
attention