Lab materials

• Slides: SQL
• Sample database: cars.db
• Interfacing samples: [sql1.c]   [sql2.c]  [sql3.c]

Lab tasks

In this lab task, you are going to interface with an SQLite3 database using the libsqlite3-dev library. You start out by adding data to the existing database in the first lab task and continue by querying the data in the second lab task.

The lab has two advanced tasks, first of which switches out the adding of the data. Second one introduces you to updating existing data rows.

Download the lab task database: study_information.db

Data model

Lab task 1 [W15-1]: Add yourself to the database

NB! The task might not be doable on the P drive due to locking issues with Windows SMB shares (unable to commit changes to the database) . To get around this, store the database file on the local computer (e.g. on Desktop) for the duration of the tasks and move to P drive after completion!

In this part you will practice doing INSERT queries. The base task does not need to be implemented in your C code! You can use the “Execute SQL” feature in the SQLite browser.

Requirements

• Write down all the SQL queries you did (just as a text document)! Show the queries once all are performed and show the database. There should be a total of 5 queries!
• ID values used for the primary key of each table  (students.id , subjects.id , declarations.id ) must not be hardcoded into your queries! They are generated automatically by the database managem system (those attributes have auto increment as a part of their database design with each table having a corresponding sequence generator).
• Perform the following insertions
  • Add yourself as a student into the database.
  • Add a subject that you have completed into the database.
  • Add 3 declarations to yourself. One to the subject that you just created and two more for subjects in the database.
• Note: grades and eID do not need to be real.

Once data is added, present the queries you performed and show you database in SQLite Browser.

Lab task 2: Retrieving data

For this lab task, you will need to write queries to retrieve data from the database. All queries need to be performed in the C program you write. You have 3 sample codes provided in the beginning of this page. Pick the one you like the most and use that as a template to writing your own queries.

Task is divided into three separately graded parts.

Requirements

• All queries for the part you intend to present must be completed. Each part is graded individually..
• Data must be completely prepared on the database engine side – any kind of calculation (sums, averages, max etc) must be written into the SQL query. No calculations in your C code!
• All relevant data must be printed. Do not print id values (e.g. subject.id, declaration.id, ..)
• Queries can either be performed through a menu selectively or can just execute one after another. Up to you.
• All resources must be released by the end of the program, no leaks – check with valgrind.

Task 2 part 1 [W15-2]: Basic data retrieval queries

First part contains basic SELECT queries.

Query 1: Find all subjects that are less than 6 credits

Query 2: Find all subjects that have an exam, ordered by the number of credits from lowest to highest.

Note: Query 1 and 2 are independent of each other. Do not tie them together.

Task 2 part 2 [W15-3]: Retrieving and combining data from multiple data tables

Second part contains more complex SELECT queries where you have to use JOIN and double JOIN to merge data from multiple tables together through their PK-FK key-pairs.

Query 1: Find all grades for students whose first name is “Marko”

Query 2: Find all classes you’ve completed, show with grades, starting from the highest grade.

Note: Query 1 and 2 are independent of each other. Do not tie them together.

Task 2 part 3 [W15-4]: Grouping data and performing calculations

In this part we will practice data aggregation for calculating for our SELECT queries. We will use both JOIN, GROUP BY and additional functions for calculating results.

Query: Find each students total earned credits and average grade

Extra task 1 [W15-5]: Adding yourself to the database more reliably

In the base task 1, likely you added data by just observing the values and hardcoding everything in. In a production database, this wouldn’t be feasible.

Information

For a better solution, we have 2 different paths we can take.

SQL  supports subqueries – queries that are a part of another query. For an example, we can embed a SELECT query inside of an INSERT query.

For an example, if we want to add another car for Marko Mets  in the sample database, we could execute

This of course isn’t perfect since there could be two people named Marko mets. However it will be good enough for the lab.

A better approach would be to insert ourselves as students first. Then get the ID value from that insertion using the query SELECT last_insert_rowid();  This will give us the ID value of that last insertion.

In a real database scenario this would be tied together with transactions so that there wouldn’t be race conditions (other people adding data to database before you get your id). However this is again unnecessary for us since we are using SQLite, which is an offline file based database.

Requirements

• Write the insertion to the database as a part of your C program code.
• If this code is executed again, make sure that a duplicate wouldn’t be created. Check before adding using a unique value (e.g. eID).
• You must use the auto-generated ID value value. Hardcoding any IDs into the query is not permitted.
  • You can use either one of the proposed approaches from the information section.

Extra task 2 [W15-6] : Changing existing data

In this task, you will practice UPDATE queries, where you will first have to identify the line and then change its attribute(s). You will need to generate and add uni-id’s to all students.

Requirements

• Generate all the students Uni-ID’s.
• Uni-IDs must be added to the database using UPDATE statements. Populate the uni_id attribute.
• Your code must work for any number of students
• You must also resolve conflicts if a Uni-ID already exists. Conflict resolution can (and should) be done in C.

After this class, you should

• Know how database is defined
• Know about basic data models – flat file, relational
• Understand data relations between tables
• Know the purpose of a database management systems
  • What to they do
  • Database vs database management system
  • some examples of widely used DBMS
• Understand the basics of SQL language
  • declarative language
  • syntax
• Be able to write basic SQL queries for
  • data retrieval from a single table
  • data retrieval and joining from two or more tables
  • inserting data into a table
• Know the benefits and disadvantages of online and offline databases
• Be able to link a C program to a SQLite3 database using libsql3 library
• Know that you can also interface with online SQL databases using libraries for specific database types

Additional materials

• SQL reference
  https://www.w3schools.com/sql/
• SQL tutorial
  https://www.tutorialspoint.com/sql/index.htm
• SQLite documentation
  https://www.sqlite.org/docs.html
• SQLite C library documentation
  https://www.sqlite.org/c3ref/intro.html
• SQLite C tutorial
  https://zetcode.com/db/sqlitec/
• SQLite in C/C++
  https://www.tutorialspoint.com/sqlite/sqlite_c_cpp.htm

Lab materials

• Slides: Trees

Lab tasks

This lab has a base task that requires you to write two programs, both performing the same task. Once written, you need to compare the performance of those two tasks. Extra task has you adding a third solution and adding it to the comparison.

Lab task [W13-1]: Comparing performance of linear search and binary search tree

For this task, you will create two programs. Both of them will count how many times each name combination occurred in the data file. For the first program, we will implement a linear search algorithm using a dynamic array as the data structure. For the second one, we will create a binary search tree.

• Download the sample applications you will base your lab task on: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/13_trees_samples.zip
• Download the lab task data file: https://blue.pri.ee/ttu/files/iax0584/andmefailid/13_trees_random_people_city_data.zip

The lab should be completed by following the step-by-step guide provided.

Requirements

• Find all the name combinations (first + last name) in the data file
• Count the number of times each name combination occurred in the provided data file
• Print the results in an output file
  • Use the following structure for the output:
    <first name> <last name> <count>
• Provide two solutions for the same task
  • First one uses a dynamic array that is expanded using realloc()
  • Second one uses a binary search tree
• Print the number of different name combinations on the screen
• Optimize your program
  • When building the binary tree, use
• Calculate the time it took your program to process the data
  • The calculation must at least include reading from the file and creation of the data structure.
  • You can also include printing and freeing.
  • Results must be comparable – if one program includes freeing in the time calculation, so must the other.
• Focus on performance
  • Avoid printing the list on the screen – this has a large performance penalty
  • When creating the binary tree, use a global variable to count the number of elements
  • For printing the results in the binary tree, use a global file pointer that is only opened and closed once during the entire program.
  • Leave the name variable in the struct statically declared – i.e. char combinedName[64]
• Before defending, prepare answers for the questions presented in the chapter #Comparing_time

Program 1: Linear search

To begin, open up the example_linear.c  and example_linear.h . Familiarize yourself with the code. Try to run it and look at the output. This will become your starter code for the first program.

Also notice that the program uses a command line arguments. To execute, use ./program_name input_file_name

Once you’ve familiarized yourself with the example code, you need to start modifying the code to fit the task.

1. Alter the data reading function
   • The current reading function works with a single name (one word). The lab task data file contains 4 fields per row – eID, first name, last name and city.
   • Alter the fscanf()  function call to work with the extra fields. You can immediately discard the eID and city – they won’t be needed.
   • Concatenate the name as "Firstname Lastname" . The concatenated form is used to both compare with the existing names and to store the name into the struct
     Hint: snprintf() helps to combine the name
     Hint: %*s  format can be used to discard a field
2. Count the number of times a name combination is present in the data file. Counting is done during reading of the data
   • Add the counter variable to the struct. Both  int or unsigned  will work.
   • Before going forward, look at how the provided example code finds non-recurrent values
     Hint: look at the return value of GetNameIndex()  function provided in the code. Make use of the return value, do not alter the GetNameIndex()  function itself!
   • The counter that was added to the struct needs to be initialized. Do it in the ReadData()  function. Think about when this initialization needs to occur!
   • ReadData()  also needs to handle updating the counter when the name is already present in the database (think about what  GetNameIndex()  returns when the name was found in the array).
3. Update the print function.
   • Alter the printing statements so that the list of names would be printed to a file
   • Change what is being printed, so it would also include the number of times a name occurred.
4. Add a print statement that displays how many different names were in the data file
5. Add freeing of the struct memory
6. Add the timers
   • Time needs to be measured in four different points. For this, it’s best to create a new structure
     
     struct TimePoints { clock_t start; /* Right before staring to read */ clock_t read; /* After the reading function finishes, before printing */ clock_t print; /* After printing to file is finished */ clock_t free; /* Data structure is freed */ };

     1 2 3 4 5 6 7

     struct TimePoints {     clock_t start; /* Right before staring to read */     clock_t read;  /* After the reading function finishes, before printing */     clock_t print; /* After printing to file is finished */     clock_t free;  /* Data structure is freed */ };

   • Place time checkpoints in your main()  function to the appropriate locations
   • To calculate the appropriate time intervals, the following function is proposed
     
     void PrintTime(struct TimePoints t) { printf("Reading: %9.6lf s\n", (double)(t.read - t.start) / CLOCKS_PER_SEC); printf("Printing: %9.6lf s\n", (double)(t.print - t.read) / CLOCKS_PER_SEC); printf("Freeing: %9.6lf s\n", (double)(t.free - t.print) / CLOCKS_PER_SEC); printf("Total: %9.6lf s\n", (double)(t.free - t.start) / CLOCKS_PER_SEC); }

     1 2 3 4 5 6 7

     void PrintTime(struct TimePoints t) {     printf("Reading:  %9.6lf s\n", (double)(t.read - t.start) / CLOCKS_PER_SEC);     printf("Printing: %9.6lf s\n", (double)(t.print - t.read) / CLOCKS_PER_SEC);     printf("Freeing:  %9.6lf s\n", (double)(t.free - t.print) / CLOCKS_PER_SEC);     printf("Total:    %9.6lf s\n", (double)(t.free - t.start) / CLOCKS_PER_SEC); }

7. Test your code without valgrind first, check the count and the output file.
8. Once the functionality is working, test the program with valgrind. When running in valgrind, you need to write arguments to valgrind before the executable and arguments for your program in the end. Running with valgrind will take approximately 1 minute to complete!
   E.g. valgrind ./example_linear random_people_city_data.txt

Testing the linear algorithm

When testing the program, the  two things to look for in the output is the number of different name combinations it found and the time it took for different parts of the program. Pay attention to the subparts and think critically whether they are realistic or not!

To validate the name counts, we’ve listed the beginning of the output file so you can compare it to yours.

Once you’ve made sure that the results are functionally correct, test the memory correctness using valgrind. This will take over a minute to run!

Program 2: Binary search tree

To begin, open up the example_bin_search_tree .c  and example_bin_search_tree .h . Familiarize yourself with the code. Try to run it and look at the output. This will become your starter code for the first program.

Also notice that the program uses a command line arguments. To execute, use ./program_name input_file_name

Once you’ve familiarized yourself with the example code, you need to start modifying the code to fit the task. The goal is to solve the same task, but by using a binary search tree.

1. Alter the struct. You need to store the name and a counter, just as with linear search
2. Alter the reading function similarly to what we did with linear search
   • Modify the fscanf()  statement to read 4 fields, you will only need the first and last name fields.
   • Concatenate the name so you can store it in a single variable.
3. Update the function responsible for inserting nodes to the tree, i.e. InsertNode()
   • Change the function parameter – the example inserts integers to the tree, we need to insert a string
   • Change the comparison statements to work with strings (instead of integers). Make sure not to cause any unnecessary performance penalties while doing so!
   • Note what happens when you try to insert a value that already exists in the tree – the example code will ignore it and not do anything. The final solution can’t ignore it. If the name already exists, we need to count up the number of times it occurred! Add an update to the counter!
4. Update the function responsible for allocating a new tree node, i.e. CreateNode()
   • Change the parameter type to suit the task
   • Add an initialization to the counter
5. Update the PrintTree()  function
   • Make alterations to work with the updated data structure
   • Note: because we are time optimizing the solution, you should make the FILE *  pointer as a global variable. Open the file before calling this function and close it after.
   • The sample print function is using “pre-order” traversal. Change the traversal mode to such that the tree would be printed in the alphabetical order. For this you need to change the order of the statements are executed to print the current node and the recursive calls to the child nodes.
6. Implement a free function for the data structure
   • Just as any tree function, this also has to be a recursive function. Take inspiration from the PrintTree()  function for how to traverse nodes. NB! You need to pick the correct traversal (pre-, in- or post-order) for the freeing to be correctly performed!
7. Add the time measurements. This can be implemented exactly the same way as you did with the linear data structure. All statements, the data structure and the print function remain the same.
8. Run your code through valgrind. You can also use command line arguments with valgrind.
   E.g. valgrind ./example_bin_search_tree random_people_city_data.txt

Testing binary search tree

For this testing section, we are not showing you the time intervals we got on our solution. The task of analyzing the measured time (are they realistic?) and comparing the time intervals is left as a task for you. This is also a part of the task defense.

Regardless of the algorithm, the number of name combinations needs to be the same, i.e. 27454.

We do offer you a look into the data file. Compare the beginning of the data file from our solution with yours!

Comparing runtime for programs

Once we’re sure about the correctness of our programs, let’s compare the runtime of both of them.

• Which program was faster, which slower?
• Was one program faster than the other one in all aspects or were there differences?
• Were there any sub components of either of the programs that took significantly different amount of time?
• Don’t forget to elaborate your answers!

Also think about how the following could affect the runtime of the programs

• The binary search tree solution contains one feature that the linear search does not have.
  • Which functionality is this?
  • How would linear search be affected if this functionality would be added?
• How would the runtime be affected by changing the realloc()  strategy from (n + 1) to (n * 2)?
• How would the programs be affected by the increase of different (non-recurrent) name combinations . Try to express it in terms of the Big O notation (https://www.bigocheatsheet.com)
• How would the programs be affected by increase of recurrences, when the number of different name combinations would remain the same?
• Think about balancing of the tree
  • Would balancing the tree affect the performance?
  • What is the worst case scenario for the binary search tree (without balancing)?
• If you solved the extra task with Trie, add it to the comparisons.

Extra task [W13-2]: Trie implementation

Create a third program to compare the efficiency. Use the trie data structure.

All the other requirements remain the same.

Recommended data structure

Compared to the sample on the slides, we don’t use a boolean true/false value to denote the end of a string (e.g. isLeaf ). Instead, we use a counter. If the counter is 0, we consider it not to be a leaf node, if the counter is > 0, it’s a leaf node where a name ends.

Hint 1: your alphabet length should also include positions for a space and a minus symbol, which are present in the names. No other special symbols are used in the file.

Hint 2: Initialization in the CreateNode()  is crucial for both the counter and the pointer array.

After this class, you should

• Be able to measure an application’s runtime internally within the program and by using a system tools
• Know how kernel time, user time, and real time are related and what they are
• Know what may happen if all processes running in parallel on the system no longer fit into the computer’s main memory
• Know the different compiler optimization levels and, at a basic level, the advantages and problems that optimization can bring
• Know concepts related to trees, such as node, root, leaf, height, etc.
• Know the types of trees and their properties (binary tree, binary search tree, and balanced binary tree)
• Know different tree traversal methods (preorder, inorder, postorder) and their use cases — when to use which traversal method
• Be able to create recursive functions for adding, searching, and deleting data in a binary tree
• Know the properties, application areas, and structure of a Trie data structure

Additional materials

• Binary search tree
  https://www.geeksforgeeks.org/binary-search-tree-data-structure/
• Binary search tree visualization
  https://www.cs.usfca.edu/~galles/visualization/BST.html
• Trashing
  https://en.wikipedia.org/wiki/Thrashing_(computer_science)

Lab materials

• Slides: Linked list

Lab tasks

In this lab, there is one base task and two estra tasks that build upon the base task.

Lab task [W12-1]: Linked list

In the base task, we are going to implement a linked list.

Download the starter code: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/12_ll_basecode.zip

Requirements

• Create a menu program that allows for manipulation of a singly linked list
• New nodes must be added to the beginning of the list only.
• A node contains a number (id) and a string (name).
  • id is auto-generated, unique, sequential integer starting from 0
  • Name is a string entered by the user during creation of the node.
  • Name is allocated dynamically, dependent on the length of the entered name.
• Implement the PrintNode() , CreateNode() , InsertNode() , FindNodeByID() , FindNodeByName()  and Unload()  functions based on their description
• Use the starter code provided as your base
• Work through the task base on the step-by-step guide. Implement the functions as specified in the guide.

Step-by-step guide

NB! Notice that the structure declaration creates 2 valid data types – struct node  and list . While both are  the same thing by definition (they are aliases from typedef), one is used in the context for referring to a single member and the other is referring to the entire list.

---

We will start by creating a function that prints out the contents of a single node. Add this function to the code file (prototype already exists in the header).  It needs to print all members of the node.

PrintNode()  function should be used whenever you need to print the contents of a node. This includes Find family of functions that you will create later.  This way, whenever the contents of the node changes, the modifications for printing only need to be made once in a single place.

Don’t forget to check for NULL pointer to avoid crashing if the calling function decides to pass a NULL pointer.

Uncomment testing stage 1 and run your code!

NB! The testing strings are in UTF-8, which is fine for our Linux machines, however they could disagree with some Windows environments. Alter the strings if necessary.

---

NB! This function is already completed for you. Pay attention to how the loop is built. You need it for traversal in the later functions.

This function is used to print the entire linked list.  It gets passed the pointer to the beginning of the list and it will traverse the list until it reaches the end of the list, indicated by a NULL  pointer..

The function also handles a NULL  pointer passed to it instead of a valid pointer to the beginning of the list – this will happen when the linked list is empty!

The function itself does not handle printing of the nodes, but rather calls  PrintNode()  on every node to print its contents. This is why we completed that first.

Uncomment testing stage 2 and run your code!

---

This function is used to create a new node and initialize its values. It returns the newly created node. Values for the node are passed as parameters.

1. Create and allocate the node
2. Assign the ID value (sequentially incrementing value, use static )
3. Allocate memory for the name and copy it over
4. Initialize the pNext  pointer
5. Return the struct pointer

NB! There are two memory allocations in this function. Both need to be checked. If there’s an error, return a NULL pointer! Program should continue running.

Uncomment testing stage 2 and run your code! Only expected changes are different address space (going from stack to heap) and increased allocations when checking with valgrind.

---

This function adds the node pNode  to the list pointed by ppHead . Double pointer is required to change the location of the beginning of the list.

In the base version of the task, add the node to the beginning of the list (onlu 2 assignment statements!)

NB! Before adding, check that pNode  isn’t a NULL  pointer!

Uncomment testing stage 3 and run your code!  Visually you should not see any differences in the output.

---

This function is what’s also called a destructor. It removes (deallocates) all nodes from them memory. This includes all the members that were allocated dynamically as well – in our case, the name.

To free a linked list, you need to loop through the entire list. To familiarize yourself with the traversal of the list, check the   PrintList()  function.

When freeing the list, you should pay close attention to how you free the current node. After freeing the current node, we no longer have access to its  pNext  pointer. Due to this, we need to create a temporary pointer that will have a copy of the current node’s address, which adds a little bit of complexity.

You have to complete 3 steps in the loop. The most elegant way of making it is by using a  while()  loop.

1. Make a copy of the current node address (you will be freeing through this copy)
2. Move the main pointer to the next element ( pCurrent = pCurrent->pNext )
3. Free the current node and its members.

Uncomment testing stage 4.  Run through valgrind. You should see 6 allocations and 6 frees.

---

In this part, we will create search functions to either search by ID or by name. The functions return the pointer to the node if a match is found or a NULL-pointer when the element was not found.

Use PrintNode()  to output the result.

Uncomment testing stage 5 and check the output! Note that the error message is provided by PrintNode() function and is not specific to the search!

---

Congratulations! All base functionality is now finished! Now create the additional functions, prompts etc so that the program could be used through the menu as a command line utility. You can delete the testing code from main.

This means prompting the user for name when inserting a node or asking for search keywords, as well as checking the returns for functions as necessary. Once that is done, present the task.

Testing

This is the final expected output of the base task

Extra task 1 [W12-2]: Alphabetically ordered list

In this task, we’re alter modify our list in order for it to be always sorted alphabetically by the name.

Requirements

• Update the InsertNode()  function in order for it to add the new node in an alphabetically sorted order.
  • Must handle adding to the beginning, end and middle of the list.
• Update the FindNodeByName()  function to take advantage of the list being sorted.
• If you completed advanced task 2 first, also update the approriate Remove()  functions to also take advantage of this property

Notes

• Adding to the beginning, end or middle of the list requires different handling of the pointers.
• Take note of the positioning and choose appropriate method of adding to the list

Extra task 2 [W12-3]: Removal of nodes

Implement the two functions to remove nodes from the list.

Requirements

• Implement RemoveNodeByName()  that removes a node from the list if it finds a matching name.
• Implement RemoveNodeByID()  that removes a node from the list if it finds the matching ID value.
• Take advantage of the ordered nature of the list (from advanced task 1)
• Ensure the integrity of the list after removing an element

Notes

• Find if the node exist in the list that you need to remove
• Removing from a singly linked list will require you to keep track of the previous node location. You cannot reuse FindNodeBy()  function (You could, if it was a doubly linked list).
• Removing from the beginning, end or middle of the list are different. Detect the position and then decide on the removal procedure!
• Don’t forget to free the memory for the node completely
• Double pointer is required to remove from the beginning of the list.

After this class, you should

• Know the properties of singly and doubly linked lists
• Know how the end of a linked list is indicated
• Understand the advantages and disadvantages of linked lists
• Know the complexity of various operations on a linked list and how it compares to arrays
• Be able to create, traverse, and free a linked list
• Be able to add elements to the beginning, end, and middle of a linked list
• Know how variables declared with the static  keyword in functions work and in which memory area they are located

Additional materials

• What is a Linked list? Types of Linked List with Code Examples
  https://www.freecodecamp.org/news/what-is-a-linked-list-types-and-examples/
• Insertion in Linked List
  https://www.geeksforgeeks.org/insertion-in-linked-list/
• Wikipedia: Linked list
  https://en.wikipedia.org/wiki/Linked_list

Lab materials

• Slides: Recursion
• Slides: Stack
• Examples done together in the lab
  • Recursive factorial: https://blue.pri.ee/ttu/files/iax0584/demokood/factorial.c
  • Tail-recursive factorial https://blue.pri.ee/ttu/files/iax0584/demokood/factorial_tail.c
  • Stack: https://blue.pri.ee/ttu/files/iax0584/demokood/stack_base.c
• Alternative example of a stack that uses the SP as a pointer:  https://blue.pri.ee/ttu/files/iax0584/demokood/stack_sp_as_pointer.c

Lab tasks

In this lab there are two base tasks, one completely independent extra task for recursion and one extra task as an extension to the stack task.

Task 1 [W11-1]: Set of recursion tasks

As the first task, you need to create three recursive programs (parts 1, 2 and 3). The task can only be presented once all three are done!

NB! The recursions are extremely simple, avoid looking for solutions on the internet!

In the beginning of the lesson, we’ll create an example of a factorial task solved recursively!

Requirements

• You can make the solution as one file with three recursions or as three separate programs. Examples are provided as separate programs.
• In all cases, the programs must support positive integers as input. Negative input either has a defined base case or will cause an error.
• Input can be asked inside of the application or read as a command line argument.
• Iterative solutions are not permitted! All three parts must be solved recursively
• Only present your task once all three parts are completed.

Part 1: Sum

Create an application that finds the sum of all positive integers until the entered integer. Negative argument for the recursive function returns the sum as 0 (no positive numbers to add, base case)

Part 2: Power

Create an application that allows you to take x to the power of y (x^y). Using the math library and built in power function is not allowed.

NB! Even though you only need to create the solution for positive integers, you can also try to expand to negative values.

Part 3: Fibonacci sequence

Create an application that finds the n-th Fibonacci number. The fibonacci numbers are calculated as the sum of two previous fibonacci numbers  fib_x = fib_{x – 1} + fib_{x – 2}. Compared to the previous recursions, Fibonacci sequence requires two base cases.

Fibonacci numbers are  0, 1, 1, 2, 3, 5, 8, 13, 21, …,

Did you notice how long it took to find the last value? This is expected in the lab and you don’t need to fix anything, however you should understand why this happened! If not, think or ask!

All 3 parts are done, now present your lab!

You can time the execution of your program using the  time  program. I’ve put the comparison of two different solutions for Fibonacci below. The second one uses tail-recursion. You can read about it on your own if necessary!

Task 2 [W11-2]: Stack

In this task, we will create a menu program to demonstrate some of the stack functions. The lab task is demonstrative only and is intended to support the dynamic memory allocation studied before – due to the added complexity of this, the benefits of speed are unfortunately diminished.

In the beginning of the lesson, we will create a partial solution with the Push() function.

Requirements

• Create a menu structure – the user must be able to select the desired operation.
• Create Pop() and Peek() functions
  • Pop() removes the topmost element from the stack and returns the value.
  • Peek() returns the topmost element from the stack, but does not remove it.
• The functions you create are not allowed to display the values themselves!  Print the values on the screen once they are returned back to the menu!
• NB! In the base variant, you are allowed to reserve a special value to be returned in the case of stack underflow, so that the illegal value wouldn’t be displayed. This is not allowed in the advanced version of this task.
• Depending on the function, implement either underflow or overflow detection!
• Pay attention to the situation when all the elements are removed from the stack – do not use realloc for 0 bytes, use the free() function!

Debugging function for the stack

In order to get a bit better understanding of the stack contents, we’ll provide a debugging function. In reality, this kind of function goes against the limitations of the stack and may also not even be possible due to the implementation specifics!

Testing

During testing, pay extra attention to

• stack overflow
• stack underflow
• freeing the data after last element is popped.
• memory leak when the program exits when there are still values in the stack

Extra task 1 [W11-3]: Practical use case for recursion

This extra task is given to you as a description of an algorithm. This is a completely independent task, that is not related to the original lab task solution!

NB! The variables in the description are given more to the likes of mathematicians (single letters). Use descriptive variable names when creating your program as is more suited for programming.

Given search key K  and an array A  of n  integers A₀, A₁, … , A_{n – 1} sorted such that A₀ ≤ A₁≤ … ≤ A_{n – 1} use the following algorithm to find if K ∈ A

1. Set lowIndex L  to 0  and highIndex H  to n − 1 .
2. Call the recursive function using 4 arguments – A, L, H, K .
   • If L > H , the search terminates as unsuccessful – return 0
   • Set m  (the position of the middle element) to the floor of (L + H)  /  2
   • If A_m < K, set L  to m + 1 , call recursion again
   • If A_m > K, set H  to m − 1 , call recursion again
   • If A_m = K, the search was successful – return 1

Once the task is complete, prepare the answer to the following questions. Once ready, present your task!

• Time complexity – compare the given algorithm and conventional linear search. How many comparisons do you need to find the result from an array that has
  • 16 members
  • 256 members
  • 100 000 members
• Give an esimate toe the complexity – e.g. constant, logarithmic, linear, exponential (https://www.bigocheatsheet.com)
• If the array wouldn’t be sorted, would the algorithm still work?

Extra task 2 [W11-4]: improving and extending the stack

In this task, we will add a two extra functions and make it a bit more universal than the original solution.

Requirements

• Add the following functions to your stack
  • Duplicate()
  • Swap()
• These functions are only allowed to use the original Push(), Pop() and Peek() functions internally to access the stack!
• Change your Pop() and Peek()  functions in a way that the following would apply
  • Stack must allow any integers (reserved values are not allowed!)
  • In the case of an underflow during popping from the stack, you can only provide a warning message, but not display the value!
• Note: You’ll likely need to adjust your Push() function as well to accomodate the additional functions

Testing

These would be the important edge cases to test for in addition to the normal operation

• Pop(), when the stack is empty (do not display any value)

• Duplicate(), when the stack is empty
• Duplicate(), when the stack is full

• Swap(), when the stack si empty
• Swap(), when the stack only has one member

After this class, you should

• Know what a recursion is, including recursive functions and data structures
• Know how to write simple recursions
• Know about the existence of a tail recursion
• Know about the good and bad that recursions bring to the table
• Know use cases for recursions
• Know what an abstract data structure means
• Know what is a stack and what are its properties
• Know the use cases for stacks
• Know how to create a stack and its mandatory functions

Additional materials

• Introduction to Recursion – Data Structure and Algorithm Tutorials
  https://www.geeksforgeeks.org/introduction-to-recursion-data-structure-and-algorithm-tutorials/
• Merge sort (recursion)
  https://www.geeksforgeeks.org/merge-sort/
• Quick sort (recursion)
  https://www.geeksforgeeks.org/quick-sort/
• Stack data structure
  https://en.wikipedia.org/wiki/Stack_(abstract_data_type)

Lab materials

• Slides:

Lab tasks

 

Lab task 1:

Requirements

Testing

Advanced task 1:

Requirements

After this class, you should

Additional materials

Lab materials

• Slides: Dynamic memory allocation 2
• Additional example: wrapper-struct for dynamic array

Lab tasks

This lab has one task that is extended by two extra tasks

Lab task [W08-1]: Reading a file dynamically

The purpose of this task is to introduce how to read an unknown length file and allocate the structure array for it dynamically in the exact length required.

Data file

Data file structure for the task: <index> <last name> <first name> <curriculum code> <points>

• Index (integer)
• First and last name – strings with varying length
• Curriculum code – string with exactly 4 characters
• Points – floating point value from 10.0 to 30.0 with a precision of 0.1.

You can use the data file generator from last week for this. To test, we’ve also provided files so you can compare your output.

Download data files here that we used in the testing part.: https://blue.pri.ee/ttu/files/iax0584/andmefailid/8_scholarship_data.zip

Requirements

• Read an unknown length data file into memory
  • Use realloc()  to read the data, expanding your memory as you are reading the file
  • Store the data into a dynamically created structure array
  • Once the reading is finished, you allocated memory size must match the exactly to how many were read from the file
  • You can only read the file once (repeat reading is forbidden, this includes just checking for newline count!)
  • The length of the file can change  – the exact length is determined during reading.
• All variable length strings must be stored in memory exactly (using dynamic memory allocation).
  • During reading, use a static buffer and then use dynamic memory to store it into the struct.
• The file contains students competing for a scholarship. Scholarships are given for 7 best students (highest points) of the following curriculums: IACB, EARB, MVEB
• Print the list of students who will receive the scholarship and also print the number of students who got it from each curriculum.
• Make sure there are no memory leaks!

Data structure for the task

For this task, we will transition into using dynamic memory for variable length strings (and other arrays) inside of our structure in order to save memory. The struct will now take the following form:

Note:

• You can alter the naming to your liking.
• The fName  and lName  are now pointers that need dynamic memory allocation due to the length being variable from person to person.
• String for the curriculum code is static because the length never changes – using dynamic memory here would be wasteful (slower and more complex).
• Single variables such as index and points remain static because again, using dynamic for those members would be making the program purposefully slower and more complex.

Recommended list of functions

NB! The actual form the functions take depends on how you tackle the task.

At minimum, you need three functions:

• Reading the data (check the next subheading).
• Printing the results.
  
  void PrintScholarships(Person *pStudents, int n); // Good for base task void PrintScholarships(StudentWrapper stdWrapper); // Good for extra task 2

  1 2	void PrintScholarships(Person *pStudents, int n); // Good for base task void PrintScholarships(StudentWrapper stdWrapper); // Good for extra task 2

• Freeing the memory.
  
  void FreeStudentData(Person *pStudents, int n); // Good for base task void FreeStudentData(Person **ppStudents, int n); // Good for base task using defensive programming void FreeStudentData(StudentWrapper stdWrapper); // Good for extra task 2

  1 2 3

  void FreeStudentData(Person *pStudents, int n); // Good for base task void FreeStudentData(Person **ppStudents, int n); // Good for base task using defensive programming void FreeStudentData(StudentWrapper stdWrapper); // Good for extra task 2

Recommended functions to make your life easier

• qsort compare function
  
  int ComparPersonByPoints(const void *a, const void *b);

  1	int ComparPersonByPoints(const void *a, const void *b);

• Printing the data of a single student (useful for printing the students who get the scholarship).
  
  void PrintStudent(Student *s);

  1	void PrintStudent(Student *s);

• For defensive programming, use the function shown on the slides
  
  void FreeMemory(void **p);

  1	void FreeMemory(void **p);

To make sure you read the file correctly, you might want to have a function that just prints everyone’s data. This is however not a part of the task.

Reading the file using dynamic memory allocation

From now, the reading function takes a new form. We need to get 2 values from the reading function – memory location of the array and number of lines read from the file. I’m proposing a three variants for this  function. Choose the one that works for you the best.

Variant 1: Most similar to the previously introduced reading function. It returns the line count and uses a double pointer for for the array.

Variant 2:  By returning the array pointer and passing the line count as a pointer, we can avoid the use of a double pointer.

Variant 3: This one uses pointers for both the array and the line count. This allows us to return the status of the function (did it succeed or failed and potentially how it failed).  This is also the most similar to the natural style of C functions – many of them return if the function succeeded or not.

Note, that using a wrapper struct (extra task 2) is also effective on cleaning up the parameter list.

Testing

In the first file, we’re using the longer data file where all scholarships got assigned. Notice the heap summary!

In the second example, I’m using the shorter data file.

Extra task 1 [W08-2]: Optimal algorithms for allocation

In this task we’re changing the algorithm how we are allocating memory to a more reasonable one.

Requirements

• Change the file reading in a way that you would be using the (n * 2) expansion strategy
  • Every time you run out of memory, you reallocate to a 2x higher amount that you have right now.
• To start, pick an initial allocation that is greater than 1 (pick a size that would be 3x lower than the file length just so you can observe the correctness).

Extra task 2 [W08-3]: wrapper struct

In this task, we’re making our code a bit more readable and contained. We will put both the struct and its properties into a wrapper to keep everything tightly integrated.

Requirements

• Put your structure array pointer into the other struct (wrapper)
• In your wrapper, you should have 3 variables – pointer to the struct, number of structs allocated, number of structs used
• Change your function parameters for the existing functions to use the new wrapper struct
• NB! Think through for which functions it is required to pass a pointer to the wrapper where it is unnecessary.

Hint: Now you will need an extra access layer to get from the wrapper to the struct itself. To help with readability, you might want to “unpack” those variables when you need to use them. See the following example.

After this class, you should

• Know how to use defensive programming to handle memory freeing
• Know the definition of a dangling pointer and how to safely handle dangling pointers
• be able to to structure your code in order to read files that can be of any length
• be able to handle changing the size of a dynamically allocated array
• be able to read data into an expanding array using dynamic memory allocation
• know all possible ways realloc works
• know the difference between (n + 1) and (n * 2) allocation strategies and be able to implemetn at least one of the two
• be able to  allocate memory to members of structures
• Know all the steps strdup() does in the background and be able to use it

Additional materials

• cppreference: Realloc documentation
  https://en.cppreference.com/w/c/memory/realloc
• Beej’s guide: Changing allocated size
  https://beej.us/guide/bgc/html/split/manual-memory-allocation.html#changing-allocated-size-with-realloc

Lab materials

• Slides: Dynamic memory 1

Lab tasks

This week we have one lab task that is extended by two advanced tasks.

Task 1 [W07-1]: random data file generator

This week, we will create a program that can generate random data files. These are useful for testing other applications without having access to real data.

Download the starter code: https://blue.pri.ee/ttu/files/iax0584/aluskoodid/7_generator_starter.zip

Requirements

• Build your application on the starter code given
• Ask the user for how many generated entries they need. There must be no upper bound!
• All entries are stored in a struct array during generation. Struct array itself is generated using dynamic memory allocation.
• Pick random first and last name and curriculum code from the pools given to you.
• Generate admission points
  • Admission points are in range from 10 to 30, ends inclusive. Precision is 0.1 points (e.g. 24.7)
• Sort the structures based on the generated last name. If last names for two entries match, order them by their first name.
• Write the output in the following format:
  <index> <last name> <first name> <curriculum code> <admission points>
  • Index is a unique integer. First entry will have the index as 0, every following one is incremented by one.
• Make sure that all resources (including memory) is freed when the program exits, use valgrind to make sure.

Qsord comparison function

I’m proposing two different comparison function options. In the first case, the type cast will be done as needed, removing the need for additional variables.

In the second case, we will create temporary pointers that take up some memory, but improve the readability of the code.

Workflow

• Create the necessary structure declaration to keep the data
• Ask the user how many entries to generate
• Allocate the memory, check the allocation!
• Generate the necessary entries
  • For every person, you must generate the entries randomly.
  • For every field from the pools, you must create a random number to pick out the member
    Hint: you can either copy the name to your struct or only keep a pointer to the name
  • In addition, you need to generate the admission points.
    Hint: Think about this mathematically – e.g. what’s the difference between 30 and 300!?! rand() function will always give you an int, regardless if what you try to do to it.
• Sort the structure array
• Write the results to an output file
• Free the allocated memory

Check with valgrind for correctness! Not only in the end, but also if you encounter some weirdness, crashes or corruption!

Testing

The output of your application should be relatively simple and short.

When looking out the output file, we see that everything is sorted by name (showing only first 15 lines)

Extra task 1 [W07-2]: output file formats

In this task, we’ll add CSV as a secondary output format for our application. User must be able to choose which output format they want.

Requirements

• Add ability to your program to generate data in the CSV format
  • First line of the CSV must be the header with the field names.
  • This will be followed by data lines. Each member is separated by a comma. NB! In CSV, we don’t put a space after the comma!
• Ask the user in which format they wish the file to be generated in (CSV or space-delimitted) and generate the appropriate data file.
• For the space-delimitted file, the extension must be .txt  and for the CSV file, use the extension  .csv .
• Make sure that the CSV is correctly generated – try to open (or import) it using  Libreoffice Calc’i  or Microsoft Office and see if they recognize the format correctly.

Extra task 2 [W07-3]: Settings

In this task, we’ll make our generation a bit more flexible and add settings to it.

Requirements

• All settings must be kept in a structure – create a new structure declaration for this!
• All settings must have default values
• Program must use the defaults if the user does not wish to change the settings. What the user needs to do to alter the settings is up to the developer
  E.g. the program could ask if they wanted to change them as the first thing it does or the user can use a specific command like argument, that allows settings to be edited.
• User must be able to alter the following settings, while inside of the program.
  • Which data fields are generated (it must be possible to turn each one of them on or off).
  • Name of the output file (only the name part. Extension must be chosen automatically based on the output format!)
  • Output format (this is from advanced task 1, move the location of the setting into the struct).
  • Number of items generated (base task part, move the location of the setting to the struct)
  • Lowe rand upper bounds for the admission points
• NB! The number of entries generated must be asked regardless if the user wished to change the settings or not. Purpose of this is just to keep all settings neatly in one struct.
• User must be shown the settings the generation will be performed under regardless if they chose to edit it or not.

Note: if you wish, you can make a settings file, however it is not necessary. The updates to settings do not need to be remembered between executions. However if you do include a settings file, make sure that the user can change those settings within the program without editing the file manually.

Hint: You can make nice use of the trinary operator here
printf("First name: %10s\n", settings.genFirstName ? "Yes": "No");

After this class, you should

• Know how to use dynamic memory allocation
• Know how to check for memory leaks.
• Know in which situations it is reasonable to use dynamic memory and in which situations you should not.
• Know the difference between function call stack and heap.

Additional materials

• Manual memory allocation
  https://beej.us/guide/bgc/html/split/manual-memory-allocation.html#manual-memory-allocation
• Memory leaks in C
  https://www.geeksforgeeks.org/what-is-memory-leak-how-can-we-avoid/
• Checking for memory leaks using Valgrind
  https://valgrind.org/docs/manual/quick-start.html

Labor materials

• Slides: Debugging
• Slides: Makefile and logging
• Additional examples: Making reusable code in the form of a  library 
• Additional reading: Fun with valgrind
• Test files for valgrind: https://blue.pri.ee/ttu/files/iax0584/demokood/valgrind.zip

Lab tasks

In this lab you have one task, which is divided into two parts. The task is extended by two extra tasks.

NB! Even though you can develop on any platform you want, one part of the proof will be to execute your program through Valgrind. Valgrind is known to work well on Linux and is known to be available on MacOS, however not on Windows. If  you wish to develop on Windows, you need to transfer the file to a Linux environment when defending.

Download the data files: https://blue.pri.ee/ttu/files/iax0584/andmefailid/6_make_data.zip

The archive contains the files for both the base and extra task!

Task part  1 / 2 [W06-1]: Reading data and processing

In the first part of the task, we need to read the data, process and print it. You will also need to demonstrate your use of compiling using a Makefile and testing memory errors using valgrind.

Requirements

• Read data from the input file
  • Data file structure
    <õppeaine nimi> <hinnete arv> <hinded>
  • Data must be stored in a structure array. For grades, you can create a reasonably sized array in the struct – e.g. 20 grades (based on the data file for the task)
• Print the following information
  • Name of the subject
  • Grades given in the subject
  • Average grade for the subject
• Keep your reading, calculating average and output in separate functions (i.e. all called from main).
• Code must be divided into two code files, which both have their own header files. Division must make sense, but details are up to you.
• Code must be compiled using a Makefile
  • At minimum, Makefile must describe the recipe all , have a variable  CFLAGS   and use the following flags for compilation:  -Wall -Wextra -Wconversion -g -fanalyzer
  • Other aspects of the complexity and structure of the Makefile are up to you!
• During the defence
  • Show compilation using a Makefile
  • Show the output through valgrind to prove that there are no issues.

Hints

The number of grades for each subject can be different, which means that every line in the file might have a different length. Due to this, we cannot read the data file with just a single fscanf()  function call like shown on previous weeks.

Due to this, we need to perform the reading of the data using nested loops

• The outer loop will read the name of the subject and the number of grades in that subject
• The inner loop will use the number of grades obtained from the outer loop to specify the number of iterations. Do not forget to check the return value of fscanf()  of the inner loop

Testing

This is an example of the code structure that you could have.

NB! Names of files are not determined, it’s just a sample. Also the data file can be in the same folder as the code files.

NB! The following output exampel doesn’t show valgrind output. Make sure to test using valgrind as well!

Task part 2 / 2 [W06-2]: Logging

In this part of the task, you need to add logging to your program.

Requirements

• Add logging for the program
  • One log per line. Logs cannot be on two lines!
  • Every log starts with a timestamp. Timestamp must contain the date (day, month, year) and the time (hours, minutes, seconds)
• When executing the program again, the logs must not be erased from the previous executions.
• Events to log
  • Opening and closing of the input file
  • Reading of the input file completed. Print the number of lines read.
  • Reading of the input file aborted due to reaching the limit of the array. Print the max size in the log. NB! You have two arrays – struct array and grades array in each struct!
  • Error calculating average grade.
• Integrity of the log must be ensured even if the program crashes
  • Option 1: You can force writing of the output buffer to the file using  fflush()
  • Option 2:Close the log file after each write – closing of the file writes the buffer to the file.
• If the log file fails to open, program must continue its work (and not exit!). Notify the user of failure.

Hints

• Prepare the string before calling the logger function! Do not overwhelm the logging function with parameters, you want it to be simple to call. To prepare the string, a good option would be to use  snprintf()
• To simplify the logger function, it is recommended to pass it the name of the file or the pointer to the log file. Some possible options:
  • Open and close the file in the log function
  • This is also one place where are global variable would not be out of place. If you wish, you can create the file pointer as a global variable (not a good solution, but an acceptable one). However an even better solution would be to complete the extra task.
• E.g. Calling the logger function might something like this:
  Logger("Program started");

Extra task 1 [W06-3]: logging library

In this task, you will create a logging library. Hint: you can use it for homework 2.

Requirements

• Add a set of .c and .g files and move your logging code there
• Add 4 levels for logging: OFF, ERROR, WARNING ja INFO – these are enums!
  • On each line of the log file, print the logging level of the message
  • Log should be only written to the file if the set logging level permits it.
    I.e.
    INFO level means that all messages will be logged;
    WARNING level means that only messages with the logging level WARNING and ERROR are logged;
    ERROR level means that only messages with the logging level ERROR are logged
    OFF means logs are not produced
• To call logger, you now needs to include the level of the log (ERROR, WARNING või INFO)
  E.g. Logger(LOG_INFO, "Program started");
• Your library must support giving a specific name to the log file
  E.g. LoggerSetOutputName("log.txt");
• Your library must support setting the logging level
  E.g. LoggerSetLoggingLevel(LOG_INFO);
• The settings for the log must be kept internally in the logging library. Settings include the log file name and logging level (you can add additional ones if you want). Keep these as global variables in your logging library.
• Settings for the logger should have default values – e.g. if developer forgets or does not want to set them up, then defaults would be used and program wouldn’t crash.
• All logs must be timestamped as described in the base task.

Extra task 2 [W06-4]: Reading simplified CSV

In this task our purpose is to show a simplified way to read names that consist of multiple words.

Requirements

• Use the simple CSV version of the input file
• Data fields are separated from each other by a comma, data fields do not contain commas.

Walkthrough

NB! We are using a simplified version of CSV files and reading then. You cannot read any CSV file in this manner! If a fields would contain a comma, this method of reading could not be used!

If you need complete CSV support, either use a library (e.g. libcsv) or write your own that could be based on a finite state machine (FSM) – you read a character and then depending on the current state and that character, you choose what to do.

---

scanf() family of function supports describing simple regular expressions for reading and describing data.

E.g. to read a time, we can use the format  scanf("%d:%d", &hours, &minutes);  – with this format, the user can enter the time as  14:35 . Variable hours  would get 14 as a value and  minutes  would get 35 . However, if the user chose to enter 14 35 , it would not match the format – hours  would still get 14 , because we didn’t expect a space in the format, the reading stops and  minutes  will be left uninitialized.

Based on this knowledge, we can compose a format   fscanf(fp, "%[^,],%d", ...)  . Replace the file pinter with your own and instead of three dots, put your variables where to store the data.

• First field will be read as a string, until the comma (comma is not read).
• Then the comma will be read out of the buffer (and thrown away)
• Then, a single integer will be read (number of grades in the subject).

This method allows you to read the first two data fields. The rest of the format for getting the grades you must make on your own (don’t forget the commas!).

After this class, you should

• be able to compose a simple Makefile
  • Know how to declare a variable and use one
  • Know how to write a recipe, including multiple recipes in a file
  • Know what goes into a recipe
  • Know about implicit rules for Makefiles
• be able to compile code using Makefiles
• Know to to use valgrind and read its output to test your programs for bugs
• Know how to get the current time inside of a program and be able to format the time string
• Know basics about logging and its importance

Additional content

• Make manual
  https://www.gnu.org/software/make/manual/make.html
• What is a Makefile and how does it work?
  https://opensource.com/article/18/8/what-how-makefile
• Compiling Programs with Make
  https://web.stanford.edu/class/archive/cs/cs107/cs107.1194/resources/make
• Makefile tutor project (sample projects with Makefile’iga)
  https://github.com/clemedon/Makefile_tutor
• Makefile tutorial
  https://makefiletutorial.com
• VMWare VSphere Logging options (levels)
  https://docs.vmware.com/en/VMware-vSphere/8.0/vsphere-vcenter-configuration/GUID-0439D577-66F7-4584-AF05-5EB41A761873.html
• An example of a logging library for C  (more complex than we need)
  https://github.com/rxi/log.c
• strftime() function
  https://www.cplusplus.com/reference/ctime/strftime/
• Valgrind documentation
  https://valgrind.org/docs/manual/index.html
• Compiling as a library guide
  http://www.yolinux.com/TUTORIALS/LibraryArchives-StaticAndDynamic.html
• Address Sanitizer documentation
  https://github.com/google/sanitizers/wiki/AddressSanitizer