Overview¶

Here is a general outline of the key concepts and commands (arranged by topic) that you should know for Exam 01.

The exam will have the following format:

1. Developer Tools/Data Allocation: Identify which commands perform certain tasks and analyze the output of debugging and tracing tools (multiple-choice, fill-in-the-blank).

2. Arrays/Stacks: Analyze, trace, and debug the implementations of a dynamic array and a stack (multiple-choice, fill-in-the-blank).

3. Lists/Queues: Analyze, trace, and debug the implementations of a linked list and a queue (multiple-choice, fill-in-the-blank).

4. Search/Sets: Analyze, trace, and debug the implementations of linear search, binary search, and a set (multiple-choice, fill-in-the-blank).

5. Sorting: Analyze, trace, and debug the implementations of various sorting algorithms (multiple-choice, fill-in-the-blank).

6. Hash Tables/Maps: Analyze, trace, and debug the implementations of a hash table and a map (multiple-choice, fill-in-the-blank).

---

Logistics¶

Exam 01 will take place during our normal lecture session on Friday, October 13 from 10:30 AM - 11:20 AM in 136 DeBartolo Hall.

---

Developer tools¶

1. How would do you use git to:

   • Create a local copy a repository.
   • Create a new branch.
   • View the changes you've made.
   • Record a change you've made.
   • Upload the changes you've made.

   • Retrieve new changes from a remote location.

2. How do you write a Makefile that utilizes rules and variables for a program that consists of multiple files?

3. How would you use gdb to debug a segfault?

4. How would you use valgrind to debug a memory error?

Data Allocation¶

1. How many bytes are common types?

   • char
   • int
   • double
   • size_t
   • int64_t

   • void *

2. How many bytes in composite types?

   • arrays

   • structs

3. Where is memory allocated?

   • stack
   • heap
   • data
   • code

Arrays / Stacks¶

1. How would implement the following dynamic array methods?

   • array_create
   • array_delete
   • array_append
   • array_insert
   • array_remove

   • array_resize

   What are the time and space complexities of the dynamic array methods?

   What does amortized mean?

2. How would you implement the following stack methods?

   • stack_push (using a dynamic array or linked list)

   • stack_pop (using a dynamic array or linked list)

   What are the time and space complexities of the stack methods?

   What does it mean for a stack to be LIFO?

   What are some applications of a stack?

Lists/ Queues¶

1. How would implement the following linked list methods?

   • list_create
   • list_delete
   • list_append
   • list_insert
   • list_remove

   • list_reverse

   What are the time and space complexities of the linked list methods?

   • With a tail pointer?
   • With a sentinel node?

   • Using a doubly linked list?

2. How would you implement the following queue methods?

   • queue_push (using a dynamic array or linked list)

   • queue_pop (using a dynamic array or linked list)

   What are the time and space complexities of the queue methods?

   What does it mean for a queue to be FIFO?

   What are some applications of a queue?

Search / Sets¶

1. How would you implement linear search?

   • On dynamic array?
   • On linked list?

   • Recursively?

2. How would you implement binary search?

   • On dynamic array?

   • Recursively?

3. How would you implement the following set methods?

   • set_add (using a dynamic array, linked list, or hash table)

   • set_contains (using a dynamic array, linked list, or hash table)

   What are the time and space complexities of the set methods?

   What are some applications of a set?

Sorting¶

1. How would you sort a sequence of values?

   • Using bubble sort?
   • Using selection sort?
   • Using insertion sort?
   • Using merge sort?

   • Using quick sort?

   What are the time and space complexities of the sorting algorithms?

   Which of these sorting algorithms are adaptive?

   Which of these sorting algorithms are stable?

   Which of these sorting algorithms use divide-and-conquer?

   How would you perform multi-factor or multi-dimensional sorting?

Hash Tables / Maps¶

1. How would implement the following hash table methods?

   • table_create
   • table_delete
   • table_insert (using linear probing or separate chaining)
   • table_lookup (using linear probing or separate chaining)

   • table_resize (using linear probing or separate chaining)

   What are the time and space complexities of the hash table methods?

   How does the load factor impact hash table performance?

2. How would you implement the following map methods?

   • map_insert (using a dynamic array, linked list, or hash table)

   • map_lookup (using a dynamic array, linked list, or hash table)

   What are the time and space complexities of the map methods?

   What are some applications of a map?