Advanced C Programming

Autumn 2015 :: ECE 264 :: Purdue University

This is for Fall 2015 (2 years ago)
Due 10/29

Linked lists #2

Goals

This assignment extends your work on hw06 with linked lists, but also includes an extra focus on algorithmic complexity. The goals are as follows:
  1. Learn how to keep data separate from containers
  2. Practice designing algorithms and data structures
  3. Practice using code that uses the following:
    1. linked lists
    2. structures for data encapsulation
    3. dynamic memory (i.e., malloc)
    4. struct initializer syntax (C99)
  4. Learn how analyze the complexity of algorithms

Prepare

Do the following before you attempt to code this assignment.

  1. Finish hw06
  2. As usual…
    1. write tiny programs to practice anything you're not solid on
    2. read this assignment description carefully

Overview

Your pick_leader(…) in hw06 implemented the plurality system of voting: voters choose one candidate as their favorite, and the candidate with the most votes wins. This is the system used in most elections in the United States.

Plurality has an obvious problem: a candidate can win even if they are not preferred by a majority (>50%) of the voters. This has been seen in numerous elections.

For this assignment, you will modify your code from hw06 to follow the instant-runoff method of choosing a winner. Each person chooses one or more favorites. If one candidate receives over 50% of the vote, then that candidate is the winner. Otherwise, the candidate with the fewest number of votes is eliminated from consideration, and the process is repeated.

Example

In this team, each person has given a list of favorites. For example, Kami's top choice is Fujita. If Fujita doesn't win, then she would prefer Baba. If neither Fujita nor Baba wins, then she would prefer Azuma. Kami has no additional preferences.

Doko gets 4 votes (40%) but fails to win a majority. Azuma and Ihara each get 2 votes (20%). Fujita and Gima each get 1 vote (10%). Fujita and Gima are eliminated since they have the fewest votes.

Doko gets 4 votes (40%). Azuma gets 3 votes (20%). Ihara gets 2 votes (20%). Baba gets 1 vote (10%). Baba is eliminated from consideration since he has the fewest votes.

Doko and Azuma are now tied with 4 votes (40%) each. Ihara gets 2 votes (20%), and will be eliminated from consideration.

Azuma is the winner with with 6 votes (60%) each.

Voting algorithms   (This part is optional and will not be covered on any exam.)

There are many voting algorithms, but none is perfect. They can be evaluated based on a variety of criteria.

criteria PASSED by instant runoff
  • majority criterion - “if one candidate is preferred by an absolute majority of voters, then that candidate must win”
  • later-no-harm criterion - “if a voter alters the order of candidates lower in his/her preference (e.g. swapping the second and third preferences), then that does not affect the chances of the most preferred candidate being elected”
  • resolvability criterion - “the probability of an exact tie must diminish as more votes are cast”
  • Condorcet loser criterion - “if a candidate would lose a head-to-head competition against every other candidate, then that candidate must not win the overall election”
  • independence of clones criterion - “the election outcome remains the same even if an identical candidate who is equally preferred decides to run”
criteria FAILED by instant runoff
  • Condorcet winner criterion - “if a candidate would win a head-to-head competition against every other candidate, then that candidate must win the overall election”
  • consistency criterion - “if dividing the electorate into two groups and running the same election separately with each group returns the same result for both groups, then the election over the whole electorate should return this result”
  • monotonicity criterion - “a voter can't harm a candidate's chances of winning by voting that candidate higher, or help a candidate by voting that candidate lower, while keeping the relative order of all the other candidates equal”
  • participation criterion - “the best way to help a candidate win must not be to abstain”
  • reversal symmetry criterion - “if candidate A is the unique winner, and each voter's individual preferences are inverted, then A must not be elected”
  • independence of irrelevant alternatives criterion - “the election outcome remains the same even if a candidate who cannot win decides to run”

// Credit: This section includes text from the Wikipedia article on Instant-runoff voting (Creative Commons Attribution-ShareAlike License)

Files

Here is what you will end up with. Most of this is copied verbatim from hw06 . Notable changes are highlighted. You will need to modify some of the other functions, as well. There are no starter files.

file contents
team.h type definitions
struct Team
=3 fields: name (string), head (of the linked list of people), and tail (of the same linked list)
struct Person
=2 fields: name (string), favorites (Favorites)
struct PersonNode
=3 fields: value (address of a struct Person), next (address of a struct PersonNode), previous (address of a struct PersonNode)
Favorites
a type for one person's favorites; create using typedef; this could be an alias for struct PersonNode* or something else of your choice
function declarations
one for each of the required functions in test.c (but not teamtest.c)
team.c function definition
create_team(char✶Xname,XintXpopulation,XstructXPerson✶Xpeople)
return type: structXTeam
create an instance of struct Team with population people
find_person(structXTeam✶Xteam,Xchar✶Xname)
return type: structXPerson✶
return the address of the first person with the given name, or NULL if not found
detach_person(structXTeam✶Xteam,Xchar✶Xname)
return type: structXPerson✶
detach and return the address of the first person with the given name, or NULL if not found
free_person(structXPerson✶Xperson)
return type: void
free the struct Person object and all heap memory that it refers to (i.e., the name)
free_team(structXTeam✶Xteam)
return type: void
free all heap memory referred to by the struct Team object, directly or indirectly; this should call your free_person(…) function; assume the struct Team object itself is on the stack; do not attempt to free the struct Team object itself
add_person(structXTeam✶Xteam,Xchar✶Xname,XFavoritesXfavorites)
return type: structXPerson✶Xperson
add a struct Person to the end of the team; you will need to copy the name; you can use strdup_(…) from hw06 for that if you like. (You may copy the strdup_(…) code.)
copy_team(structXTeam✶Xteam)
return type: structXTeam
make a deep copy of a team; not only will the struct Team object be a copy, but every struct Person (including their name fields) will be a new copy
pick_leader(structXTeam✶Xteam)
return type: structXPerson✶
return the person who is winner using the instant-runoff method of voting; this function must not modify the team or any dat that it refers to (directly or indirectly); when a candidate is “eliminated” from consideration, it is not removed from the list of people that team refers to; Hint: there are many reasonable ways to do this, but you might find arrays to be more helpful than linked lists
Clarification: return NULL if all candidates are eliminated (i.e., unbreakable tie); a candidate is the winner if they get greater than 50% of the votes; for example if A's favorites are {A, B}, B's favorite is {B}, C's favorite is {C}, and D has no favorites ({}), then A, B, and C will be eliminated as candidates in round 1. pick_leader(…) should return NULL.
create_favorites(structXPerson✶Xfirst_choice,X...)
return type: Favorites
create a Favorites object with the specified people in the order to be passed; this will become the favorites field of struct Person; any memory allocated by this function must be freed by your free_person(…); the last item in the list must be NULL
add_favorite(structXPerson✶Xfan,XstructXPerson✶Xfave,XintXrank)
return type: void
add fave to fan's favorites at the specified rank; rank is 0-based; a negative rank indicates the position relative to fan's last choice; call with rank=0 to set the person's top choice, with rank=1 to set their second choice, rank=-1 to set their last choice, rank=-2 to set their second to last choice, and so on.
teamtest.c function definitions
main(intXargc,Xchar✶Xargv[])
return type: int
test your functions in team.c; comprehensive and original; must have a return statement
create_test_team()
return type: structXTeam
create an array (on the stack) of ≥4 people (struct Person) using C99 compound initializer syntax and then pass that to your create_team(…) to create a new struct team object; limit: 2 statements; the first statement must declare/initialize an array of struct Person objects. The second statement must call create_team(…); your create_test_team(…) will return a struct Team; people should be in the same order as in the array (Hint: You can refer to the name of a struct object even within its initializer.)
fprint_team(structXTeam✶,XFILE✶Xstream)
return type: void
print the team's name, leader's name, and members to stdout in the following format:
Modern Jazz Quartet
- leader:  John Lewis
- members: Milt Jackson (favorite: John Lewis)
           John Lewis   (favorite: Percy Heath)
           Percy Heath  (favorite: John Lewis)
           Connie Kay   (favorite: Milt Jackson)

This will need to call pick_leader(…) since the leader is not stored in the struct Team. Use fprintf(stream, …) in this function. When you test in your main(…), test with fprint_team(&team, stdout). (Note that fprintf(stdout, …) is equivalent to printf(…).) Use spaces, not tabs. Exactly one space should separate the end of the longest name (e.g., "Milt Jackson") and "(favorite: …)". Each line ends with "\n" and. Additional spaces before the "\n" are not allowed. Display members in the order they were added to the team. This specification is precise. Your output should match exactly.
Clarification: When there is no leader—i.e., pick_leader(…) returned NULL—print “(null)” in place of the favorite's name. When a person does not have any favorites, print “null” in place of their favorite. This is exactly the same as the example shown in hw06 .
Type all declarations into your program manually. Do not copy-paste. (You learn more from typing code manually.)

Doing the assignment

Use test-driven development to do this assignment incrementally.

  1. Start with your working teamtest.txt and teamtest.c from hw06 .
  2. Comment out everything in your main(…).
  3. Compile and use diff to check that the output agrees perfectly.
    gcc -o teamtest teamtest.c team.c && ./teamtest | diff teamtest.txt -
  4. One by one, add in each step from your main(…) until you have all of the functionality.
    1. Create an empty team.
    2. Create a team with one person who has no favorites.
    3. Create a team with one person who is their own favorite.
    4. Create a team with two people who are each other's favorite (but still only one favorite per person).
    5. Create a team with two people who have both of the two people in their favorites (i.e., 2 favorites each).
    6. Make your fprint_team(…) work sufficiently to handle your team with one person.

Your code should never be broken for more than about 10-15 minutes. If you are not doing this, you are taking longer than necessary to do the assignment.

Requirements

  1. As with hw06
    1. Your submission must contain the files specified in the overview and your teamtest.txt (as usual).
    2. All data referenced by a Team structure must be on the heap. That includes all struct Person objects, their names, and the team name. The struct Team object itself may be on the stack.
    3. Make no assumptions about the number of people on a team, or the length of a person's name.
    4. Your teamtest.c must be your own, and must test all functionality.
    5. Struct types may not have any additional fields, other than those shown above.
  2. pick_leader(…) must not have any “side effects”. In other words, it must not modify the state of the team that was passed in, or any of the data it refers to (directly or indirectly). For example, it might be tempting to delete people from the list of people in the team that was passed in, but that would not be allowed.
  3. Only the following external header files, functions, and symbols are allowed. (All others are prohibited.)
    header functions/symbols allowed in…
    stdlib.h malloc(…), free(…) team.c, team.h, teamtest.c
    stdarg.h va_arg, va_list, va_copy, va_start, va_end team.c, team.h, teamtest.c
    stdbool.h true, false team.c, team.h, teamtest.c
    string.h strlen(…), strcmp(…), strcpy(…) team.c, team.h, teamtest.c
    stdio.h fprintf(…), stdout teamtest.c
    assert.h assert(…) team.c, team.h, teamtest.c
  4. As usual…
    1. Do not use dynamic arrays (C99 feature, e.g., char s[n];)
    2. Code must successfully compile and run with your teamtest.c and any other valid test file.
    3. Code must meet all requirements in the Course Policies and Code Quality Standards.
      Note: If you choose to use assert(…), be sure you understand the specific guidelines that relate to it.

How much work is this?

This assignment is not easy, but it is expected to require about half as much effort as hw06 . (Your mileage may vary. Do not depend on this estimate.)

The main work will be to find an algorithm for your new pick_leader(…). Before that, you will need to make some changes to the rest of the code to accomodate storing a sequence of favorites in each person, instead of just one favorite. If you understood hw06 well, then this part should be very straight-forward.

As with all things involving dynamic memory, expect to spend some time debugging unless you have gotten very solid on these concepts and proficient using gdb and valgrind.

Q&A

  1. What should my Favorite type be?
    It is your choice. One option is to make Favorite an alias for struct PersonNode*, but you are free to set it to any other type that you think will make your work easiest for implementing the rest of this. Keep in mind that the user of your code (i.e., someone calling your functions from their program), must not need to be aware of anything about what your Favorite type contains.

    If you are completely confused, it may help to review how typedef works. Remeber that your team.h will contain exactly 4 type definitions. When referring to your Favorites type elsewhere, you will not use the struct keyword before it. See the function signature for add_person(…), for example.
  2. Why is create_favorites(…) specified as a variadic function? Why not just pass an array?
    This makes your create_test_team(…) a lot cleaner and shorter, and allows us to keep the requirement of two lines in create_test_team(…).
  3. Doesn't the output format of fprint_team(…) need to change to accomodate multiple favorites per person?
    Nope. A person's "favorite" is still their first choice. Let's keep it simple and leave the format as is.
  4. Can one of a person's favorite be someone outside the team?
    Yes. It is acceptable to have someone from outside the team included in a person's favorites list, but they may not win. pick_leader(…) will only return a person who is a member of the given team.
  5. What if there is still a tie, even with instant runoff?
    Return NULL to indicate that no leader could be chosen.
  6. What is assert(…)?
    We haven't covered this, but someone asked if they could use it. Since it is useful and we will cover it later, there is no reason not to allow it for those who have figured it out on their own.

    In short, assert(…) is a macro that helps you catch bugs early. You call it with a condition (e.g., assert(head == NULL);). If the condition is false, your program will crash right there. That's a good thing because it help you to catch bugs early. It also helps you document your expections about the state of particular variables at specific points in your code. For example, if you have a branch of an if statement that should only happen when head == NULL, then this statement shows the reader that head == NULL if execution passed that point.

    We will discuss assert(…) properly in class later.
  7. Will the caller use Favorites for anything else?
    No.
  8. Can the same person appear twice in another person's favorites?
    You may assume that won't happen.
  9. How can I ensure that create_favorites(…) can access the names of the people being passed to it?
    This is not necessary. You don't need to access or copy the name of the person within create_favorites(…). That can be done in create_team(…). You may assume that the Person objects referred to when create_favorites(…) is called will still exist when create_team(…) is called.
  10. May we assume the struct Person objects passed (by address) to create_favorites(…) will still exist when create_team(…) is called?
    Yes.
  11. What if the rank passed to add_favorite(…) is out of bounds?
    You may assume that won't happen, i.e., |rank| ≤ the team's population.
  12. Should we count votes for people not currently on the team?
    Keep those people in the favorites lists, but ignore them when counting votes. Skip over them, as if they had been eliminated in a previous round.
  13. Can we use Favorites* instead of Favorites in our struct Person?
    No.
  14. Can Favorites be an address type?
    Yes. The following is one possibility. (Feel free to use/copy as is.)

    typedef struct PersonNode* Favorites;

    Here is a very simple example of using typedef to create an address type that hides the star. In this case, T is an alias for S*.
    #include <stdio.h>
    struct S {
        int x, y;
    };
    typedef struct S* T;
    int main(int argc, char *argv[]) {
        struct S s = {.x = 4, .y = 5};
        T t = &s;
        printf("s.x ===== %d ... s.y ===== %d\n", s.x, s.y);
        printf("t -> x == %d ... t -> y == %d\n", t->x, t->y);
        return 0;
    }
  15. How should create_test_team(…) be structured?
    The basic format is very similar to the one used in hw06. (Feel free to copy/use this.)
    struct Team create_test_team() {
      struct Person people[] = {
        { .name="…", .favorites=create_favorites(&people[…], &people[…], NULL) },
        { .name="…", .favorites=create_favorites(&people[…], &people[…], NULL) },
        { .name="…", .favorites=create_favorites(NULL) },              // no favorites
        { .name="…", .favorites=create_favorites(&people[…], NULL) },  // 1 favorite
      };
      return create_team("…", sizeof(people)/sizeof(*people), people);
    }
  16. Where should the favorites be allocated?
    It's up to you, but you probably want to have your create_favorites(…) create the container (e.g., a linked list) to hold the struct Person objects that are passed to it. However, it will not allocate memory for the struct Person objects themselves.
  17. Can I allocate the struct Person objects in my create_favorites(…)?
    It is not directly prohibited by the requirements, but you probably wouldn't want to. This is just like in hw06. If three people vote for the same person (i.e., have that person in their favorites), you want the ultimate structure to refer to the same struct Person obhject. Therefore, it will need to be created outside create_favorites(…). You will do this from your create_team(…).

    Also, this wouldn't work at all with your create_test_team(…) because it needs to be 2 statements. It is possible to pass the address of an element of people to create_favorites(…), even within the initialization of people, if create_favorites(…) tries to access that memory, it will result in an error because at the time create_favorites(…) is called, people hasn't been initialized, yet.
  18. Should I use add_favorite(…) in my create_favorites(…)?
    You may if you like, but it probably won't be useful.
  19. Should I use create_favorites(…) in my create_team(…)?
    You may if you like, but it probably won't be useful.
  20. How can I reuse code?
    There are many perfectly reasonable and correct ways to structure your code for this assignment.

    You might find it useful to create a couple general purpose helper functions at the top of your team.c. Here are a couple examples. You don't have to use these, but you may use/copy if you wish.
    void _add(struct Person* p, struct PersonNode** head, struct PersonNode** tail, int idx);
    // Add a person at position idx in any given linked list
    
    void _connect_all_favorites(Favorites favorites, struct Team* team);
    // Replace every Person* in favorites with the address of the one with the
    // same name in the given team
    
  21. How do we add a favorite who is not on the team?
    This can't be done from your create_test_team(…) but it could easily be done from your main(…). Just create a struct Person object (most likely on the stack) and then, in a separate statement, pass it to create_favorites(…).
    struct Person outsider = { … };
    struct Person people[] = { &outsider, … };
    struct Team team = create_test_team("…", sizeof(people)/sizeof(*people), people);
  22. What should pick_leader return if there all candidates are eliminated (i.e., unbreakable tie)?
    NULL
  23. What should fprint_team(…) print when pick_leader(…) returns NULL?
    (none)
  24. What if eliminating multiple losers in one round results in eliminating what would otherwise be a clear winner??
    At each round, just eliminate the candidate(s) that have the least number of votes in that round. Once a candidate has been eliminated, they are permanently eliminated, even if they were somebody's later choice.

    Example:
    • A's favorites are A and B
    • B's favorite is only B
    • C's favorite is only C

    In round 1, A, B, and C all get one vote each, so all are eliminated. Since B was eliminated in round 1, B has been permanently eliminated and is not considered in round 2. This was illustrated in the example shown at the beginning of this assignment.

Updates

10/17/2015: fixed signature on add_favorite(…)

10/20/2015: fixed typo in screenshot ("Empty" ⇒ "Some Empty Team"); clarified that teamtest.txt must be turned in along with team.c, team.h, and teamtest.c.

10/23/2015: the last item in create_favorites(…) must be NULL

10/24/2015: clarified: stdarg.h is allowed; added return types to overview table; added Q7-Q11 to Q&A's (more might be added later today)

10/24/2015: Added Q12-Q21 in the Q&A

10/29/2015: Added Q22-Q24 in the Q&A; added minor clarifications to pick_leader(…) and fprint_team(…) to deal with cases of no leader and/or no favorite(s)