1,721,081 research outputs found
Advanced Programming and Problem-Solving Strategies in C. Part IV: Exam-Based Problems
No full textPrevious parts provide a comprehensive introduction to the C language syntax, and the modern study of computer algorithms and data structures. Following those parts, this book presents many solutions to problem-based examinations using the C language. Problems are extracted from examination tests of the "Algorithms and Programming" course delivered within the Computer Engineering Bachelor-level degree at Politecnico di Torino. The text is intended primarily for use in undergraduate or graduate courses in algorithms and data structures. The content of the previous parts should be considered as prerequisites for reading this book. We have attempted to make every problem accessible and interesting. We also provide careful explanations of the main mathematical and algorithmic issues. The volume is divided in two chapters. The first one includes only completely solved examination-based problems. Those correspond to 16 examination tests, i.e., 16 standard and 16 simplified examination tests, for a total of 64 completely solved exercises. The second chapter includes only suggested problems, taken from 10 mock examination-based tests, again each one including a standard and a simplified section, for a total of 40 suggested problems. As in the examination of "Algorithms and programming", those exercises mainly include the following topics: Sorting, static and dynamic data structures, recursion, abstract objects, collections of objects and abstract data types (ADTs), trees, symbol tables (such as Binary Search Trees, BSTs, and Hash Tables), and graphs. Simplified exercises target the guided development of the solution to a problem, with only a small emphasis on design and problem-solving skills and more emphasis on the ability to use advanced C features (pointers, dynamic allocation, recursion) and on the knowledge of basic data structures and algorithms. For those simplified problems, only the code required by the examination specification is reported in the text, i.e., clients, data definitions and data initialization are often not reported in the book for the sake of space. Standard exercises target the design and development of a program in C to solve a problem, the main emphasis being on the algorithm and data-structure adopted, and on problem-solving and design skills. Exercise and solution style follow the ones introduced in previous volumes by the same author. C syntax is somehow restricted to the minimum set of constructs, avoiding useless or redundant ones. Solution design is maintained as simple as possible, keeping in mind asymptotic time and memory costs. Each solution can be mono or multi-file. In this last case, book sub-titles specify the file name to correctly follow the inclusion of header files and type definitions. Solutions are usually introduced by short descriptions, illustrating the main philosophy and core ideas behind them. Simplified specifications (but sometimes even standard ones) may be followed by more than one solution, illustrating the main logic possibilities to reach the same final target. The book is also covered by online material, as all source codes are available on the editor web page. We would sincerely appreciate any comments, criticisms, corrections and suggestions for improving the text. Please address all correspondence to: [email protected] or visits the following web page: http://fmgroup.polito.it/quer
Advanced Programming and Problem-Solving Strategies in C. Part II: Algorithms and Data Structures
No full textThis book presents computing technologies for university students enrolled in advanced programming classes such as "Algorithms and programming", and software development professionals. It will give the reader an informative, challenging ad entertaining introduction to use C language to solve complex problems. Those problems will include advance algorithms and complex data structures. The book will concentrate on complete working programs, somehow presenting and contrasting several possible solutions. This work assumes a general-purpose knowledge of the C language such as the one usually learned during basic programming courses delivered at the first year of the curricula in computer engineering and computer science. The book main highlights are the following: - Extended coverage of pointers, dynamic arrays and matrices, linked-lists, and other basic data structures. - Abstract data types (ADTs). - Recursions and recursive algorithms. Each topic is covered by a rich collection of partial and complete examples, and about 100 fully implemented and debugged programs. The focus is on good software engineering, and on program clarity, such that the reader is guided to learn properties of algorithms and data structures as fast as possible. The content of each chapter is the following: - Chapter 1 presents a revising set of exercise to recall basic C construct and problem solving strategies. This is essentially a very brief summary of Volume I by the same author. Code and programming style follow the same book. - Chapter 2 covers dynamic memory allocation. Pointers, operators on pointers, dynamic arrays, and dynamic matrices are covered into details. - Chapter 3 presents dynamically allocated lists. Simple, ordered, bi-linked, circular, and list-of-lists are described with several figures and code segments. - Chapter 4 describes basic concepts for recursion and it presents simple recursive programs. - Chapter 5 includes standard recursive problems such as merge-sort, quick-sort, the eight queen problems, etc. It also describes combinatorics problems, such as: The multiplication principle, simple arrangements, arrangements with repetitions, simple permutation, permutation with repetitions, simple combination, combinations with repetitions, and the power-set. - Chapter 6 describe how to apply recursion to some hard-to-solve problems. - Chapter 7 describes all required concepts to write programs "in the large", i.e., multi-file programs, with personalized header files. It also illustrates the main concepts of Abstract Data Type (ADTs) and their use in C programming. - Chapter 8 illustrates several ADT-based problems, such as the stack (based on an array or a dynamic list), queues, etc. The book is also covered by online material, as all source codes are available on the editor web page. We would sincerely appreciate any comments, criticisms, corrections and suggestions for improving the text. Please address all correspondence to: [email protected] or visits the following web page: http://fmgroup.polito.it/quer
Model checking evaluation of airplane landing trajectories
No full textComputing trajectories of a set of airplanes in their final descent is an important problem in air traffic control.
It consists of deciding a trajectory, the runway, and the landing time for each airplane, such that several constraints are satisfied, while optimizing flying (fuel) costs, and minimizing waiting times.
To solve this problem, we model it as a discrete game, the "k-king" puzzle, in which each airplane is represented (and it moves) as a king chess-piece on a chess-board.
Although the model has already been introduced in the past, we propose several extensions, taking into account different aspects of the real problem, such as constrained airspaces, distinct airplane speeds, various separation distance among airplanes, and specific restrictions in the landing trajectories.
Moreover, we model both "static" and "dynamic" cases for 2D and 3D airspaces.
On these extensions, we describe an "exact" resolution method based on ideas and algorithms coming from the formal verification of correctness of hardware devices and software tools area.
Furthermore, to improve the size, and complexity, of the models we are able to deal with, we propose a decomposition technique based on the divide-and-conquer paradigm.
This solution, which we call "Plane by Plane" decomposition, trades-off between accuracy and efficiency, i.e., exact solutions degrade to non-optimal ones to maintain scalability.
We finally propose an implementation of this algorithm based on (and taking advantages of) modern multi-core, multi-threaded, systems.
We present a detailed description of the model and the algorithms, as well as our computational results for quite large static and dynamic 2D and 3D problems
Back to Basics: Solving Games with SAT
No full textGames became popular, within the formal verification community, after their application to automatic synthesis of circuits from specifications, and they have been receiving more and more attention since then. This paper focuses on coding the "Sokoban" puzzle, i.e., a very complex single-player strategy game. We show how its solution can be encoded and represented as a Bounded Model Checking problem, and then solved with a SAT solver. After that, to cope with very complex instances of the game, we propose two different ad-hoc divide-and-conquer strategies. Those strategies, somehow similar to state-of-the-art abstraction-and-refinement schemes, are able to decompose deep Bounded Model Checking instances into easier subtasks, trading-off between efficiency and completeness. We analyze a vast set of difficult hard-to-solve benchmark games, trying to push forward the applicability of state-of-the-art SAT solvers in the field. Those results show that games may provide one of the next frontier for the SAT communit
Guida alla programmazione in linguaggio C. Volume I: Fondamenti di programmazione
No full textLa seconda edizione presenta un aggiornamento dei contenuti allo scopo di rendere il testo più fedele ai programmi dei corsi di informatica di base del Politecnico di Torino così come strutturati recentemente. Questo ha comportato: 1. L'eliminazione degli argomenti relativi alla gestione dinamica della memoria, non più trattata nei corsi del primo anno. 2. L'eliminazione di alcuni esercizi di maggiore difficoltà logica. 3. La creazione, in ogni capitolo, di una sezione di esercizi proposti che estendono quelli precedentemente risolti e costituiscono un'ottima base per un approccio autonomo al "problem solving". La soluzione di tutti gli esercizi, tanto quelli "risolti" (la cui soluzione è già presentata nel testo), quanto quelli "proposti", è inclusa nel materiale elettronico associato al volume. Tale materiale, invece di essere fornito su CD, come nella versione precedente, è reso disponibile tramite il sito WEB dell'editor
A Fast MPEG's CDVS Implementation for GPU Featured in Mobile Devices
Full text linkThe Moving Picture Experts Group’s Compact Descriptors for Visual Search (MPEG’s CDVS) intends to standardize technologies in order to enable an interoperable, efficient, and cross-platform solution for internet-scale visual search applications and services. Among the key technologies within
CDVS, we recall the format of visual descriptors, the descriptor extraction process, and the algorithms for indexing and matching. Unfortunately, these steps require precision and computation accuracy. Moreover, they are very time-consuming, as they need running times in the order of seconds when implemented on the central processing unit (CPU) of modern mobile devices. In this paper, to reduce computation times and
maintain precision and accuracy, we re-design, for many-cores embedded graphical processor units (GPUs), all main local descriptor extraction pipeline phases of the MPEG’s CDVS standard. To reach this goal, we introduce new techniques to adapt the standard algorithm to parallel processing. Furthermore, to reduce memory accesses and efficiently distribute the kernel workload, we use new approaches to store and retrieve
CDVS information on proper GPU data structures. We present a complete experimental analysis on a large and standard test set. Our experiments show that our GPU-based approach is remarkably faster than the CPU-based reference implementation of the standard, and it maintains a comparable precision in terms of true and false positive rates
Algoritmi e programmazione: richiami di teoria con prove d'esame ed esercizi svolti
No full textQuesta pubblicazione raccoglie, organizza e risolve numerosi esercizi di teoria che coprono gli argomenti trattati nel Corso di "Algoritmi e programmazione". Ogni capitolo del volume è strutturato come segue: - richiami dei fondamenti teorici - svolgimento completo di almeno un esercizio significativo per argomento - esercizi con soluzione, ma senza procedimento - proposta di esercizi non risolti, che si pensa costituiscano un utile stimolo al lavoro individuale. La suddivisione in capitoli segue lo schema successivo. - Capitolo 1: algoritmi iterativi di ordinamento interno - Capitolo 2: algoritmi ricorsivi di ordinamento interno - Capitolo 3: analisi della complessità mediante le equazioni alle ricorrenze - Capitolo 4: alberi binari - Capitolo 5: alberi binari di ricerca e loro estensioni - Capitolo 6: tabelle di hash - Capitolo 7: heap, heap sort e code a priorità - Capitolo 8: risoluzione dei problemi mediante programmazione dinamica \item - Capitolo 9: risoluzione dei problemi con il paradigma greedy - Capitolo 10: visite dei grafi e loro applicazioni - Capitolo 11: alberi ricoprenti minimi - Capitolo 12: cammini minimi da una singola sorgente - Capitolo 13: temi d'esame di teoria risolti. I primi dodici capitoli, quindi, presentano tutti argomenti specifici, suddivisi in maniera opportuna, riassumendone gli aspetti teorici e riportandone numerosi esercizi. Il Capitolo 13 invece include tutti gli argomenti analizzati nei capitoli precedenti, includendo ogni tipologia di esercizio in maniera ortogonale, così come accade abitualmente nei temi d'esame del corso di "Algoritmi e programmazione" del Politecnico di Torino. Argomenti e esercizi, sono stati selezionati in base alla lunga esperienza degli autori, da anni coinvolti in corsi di programmazione, algoritmi e strutture dati di base e avanzati. Chiunque rintracciasse errori sfuggiti agli autori è pregato di segnalarlo per posta elettronica agli autori stessi, utilizzando i seguenti indirizzi: [email protected] [email protected]
- …
