Exercises for the week 7 exercise session¶

Exercise Session Instructions

Please read the following instructions carefully to ensure smooth conduct during the exercise session.

1. Forming Groups

Each student is free to select their own group members. Each group must consist of no more than 4 members. In Zoom, you will be able to use the breakout rooms feature to work in your groups.

2. Exercise Session

Each group must collectively work on at least one of the exercises provided: Task 1 (Odd numbered groups (group 1, group 3, etc) start with this) or Task 2 (even numbered groups (group 2, group 4) start with this). The group should take no more than 45 minutes to work on that task (At most, until the end of the session). In both tasks, the group should discuss and design a solution to the problem. The group should also discuss the asymptotic performance of their solution.

Leaving the session early

If a group manages to finish working on the exercise before the end of the session, the group may leave as soon as they've sent the email to the course assistant.

3. Email Submission

Upon completion, one member from each group is required to send an email with the groups solution for review. Follow the guidelines below for the email submission:

To: jaakko.rajala@tuni.fi
Cc: The rest of the group members' emails
Subject Format: [Session Date] - [Group number] - [Task Number] - [Group Member Names]
Example Subject: 2023-10-12 - Group 1 - Task 1 - Alex, Jordan, Taylor, Jamie
Body: Include all group members' and name their main responsibility or contributions during this group activity.
Attachment: Attach the groups solution (A C++ file) to the email. Make sure relevant information such as asymptotic performance of each relevant function or thought process is visible in comments.

Note: Please ensure that the email is sent before the end of the exercise session!

Attention: Emails not adhering to the format may not be considered for evaluation. Ensure compliance with the format to avoid inconvenience.

Task 1¶

You need a program to build family trees, i.e. maintain information about relatives of people. Program can be fed information about individual people, and the relationships can be formed between people (parent-child and marriages). Based on C++ standard library, design a datastructure to store the family tree. All people have a unique id (social security number or similar), name, sex, birth year and possible year of death. The program should be able to efficiently check if two people are relatives. How would you design the program using STL data structures?

Task 2¶

You have to implement a “contacts app” with the following properties: new contacts (name, phone number) can be added, old contacts can be removed (based on name), contacts can be searched based on name. Insertions and removals happen in bursts but happen seldom, searches happen often. You must store the data in a single std::vector, but you are allowed to write your own structs, if you want. How would you best implement the operations? What would be their performance?