# Exercises 1

Deadline 2025-10-24 23:59

All filenames refer to the g0.complang.tuwien.ac.at.  You should
perform your measurements on this machine.

## Submission

A plain text file containing just the questions is available at
`/usr/ftp/pub/anton/lvas/efficient/25/Exercises1.txt`.  Please create
a subdirectory `1` in your git project, copy that file there, and
answer the questions with a text editor, inserting parts of the
transcript where needed.  For answers where the supporting evidence is
longer, put the supporting evidence in a file (or several) in the same
directory.  Don't forget to commit and push the directory and the
relevant files before the deadline.

Please do not just answer the questions, but document how you arrived
at the answers (this is also useful for preparing yourself for the
interview part of the exam later in the semester).  A good way to do
that for some questions is to provide transcripts of your shell
sessions.  You can either cut-and-paste the text from the terminal
session, or use `script -f <filename>` to write the transcript to the
named file (and then copy parts of this transcript into your
`Exercises1.txt`.

## Setup for questions Q1-Q6

There are programs

````
/usr/ftp/pub/anton/lvas/efficient/25/q1a
/usr/ftp/pub/anton/lvas/efficient/25/q1b
/usr/ftp/pub/anton/lvas/efficient/25/q1c
/usr/ftp/pub/anton/lvas/efficient/25/q1d
/usr/ftp/pub/anton/lvas/efficient/25/q1e
````

They run on the command line and take no parameters.

You need only one transcript for all the programs to answer the
following questions, but point out in your answer where

### Q1: Which of these programs are fast enough?  Why?
### Q2: Which of these programs are CPU-bound?
### Q3: Which of the CPU-bound programs spend most of their time in user mode?
### Q4: Which of the CPU-bound programs spend most of their time in system mode?
### Q5: Which program consumes the most memory?
### Q6: Which program consumes the most CPU time?

## Setup for questions Q7-Q11

The source file
`/usr/ftp/pub/anton/lvas/effizienz-aufgabe23/magichex.c` can be
compiled with

````
gcc -O /usr/ftp/pub/anton/lvas/effizienz-aufgabe23/magichex.c -o magichex
````

and the resulting binary can then be run with, e.g.:

````
./magichex 3 0  
````

(Append `>/dev/null` to avoid cluttering your transcript with the
output).

This is the invocation you should use for answering the questions below.

Show the relevant parts of the output of gprof along with the answers
for the following questions.

For answering the questions that deal with coverage, make sure to
delete `magichex.gcda` (if present) before making the run for
producing your data; otherwise the results of multiple runs will
accumulate in `magichex.gcda`; your answer should only be about one
run with the invocation above.

### Q7: Which function consumes the most time according to the profile?
### Q8: Which function is called most often?
### Q9: Which function calls `sethi` most often
### Q10: Which function is called by `lessthan` most often?
### Q11: According to the `gcov` output, which line in `solve` is executed most often?